Given an array of \(N\) integers \(\{a_1, a_2, a_3, ..., a_N\}\), sort the array in non-descending order using the insertion sort algorithm, starting at \(a_1\) and ending after inserting \(a_N\).

Input Specifications

The first line of input will contain \(N\) \((1 \le N \le 10^3)\).

The second line of input will contain \(N\) space-separated integers, representing each element \(a_i\) \((0 \le a \le 10^6)\) in the array.

Output specification

Output the final state of "pass", where a pass is defined as each time we insert the next value into our sorted array.

Sample Input 1

9
25 9 11 31 23 2 42 15 26

Sample Output 1

25 9 11 31 23 2 42 15 26
9 25 11 31 23 2 42 15 26
9 11 25 31 23 2 42 15 26
9 11 25 31 23 2 42 15 26
9 11 23 25 31 2 42 15 26
2 9 11 23 25 31 42 15 26
2 9 11 23 25 31 42 15 26
2 9 11 15 23 25 31 42 26
2 9 11 15 23 25 26 31 42

Sample Input 2

1
0

Sample Output 2

0