The Cocktail Shaker Sort Algorithm is another variation of the Bubble Sort Algorithm where instead of only traversing the array from left to right, we also go from right to left once we reach the right side.

Given an array of \(N\) integers \(\{a_1, a_2, a_3, ..., a_N\}\), sort the array in non-decreasing order using Cocktail Shaker Sort.

*Note: although there is no penalty for this problem, ensure that you increment the lower bound with each loop to avoid comparing already sorted portions of the array!

Input Specification

The first line of input will contain \(N\) \((1 \le N \le 200)\).

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

On separate lines, output \(N\) space-separated integers representing the final state the array after each swap.

Sample Input 1

9
25 9 11 31 23 2 42 15 26

Sample Output 1

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

Sample Input 2

1
0

Sample Output 2

No lines of output.