Given you an integer sequence of length n.

Please use insertion sort to sort this sequence in ascending order.

And output the sorted sequence in order.

Input Format

Input consists of two lines:

• The first line contains the integer n
• The second line contains n integers (all integers are in the range of 1~10⁹), representing the entire sequence

Output Format

Output consists of one line, containing n integers, representing the sorted sequence.

Data Range

1 ≤ n ≤ 1000

Sample Input

5
3 1 2 4 5

Sample Output

1 2 3 4 5