Problem C
Turbo
Frane has been given the task of sorting an array of
numbers. The array consists of
-
In the first phase, the number
is moved to position by repeatedly swapping consecutive elements. -
In the second phase, the number
is moved to position in the same manner. -
In the third phase, the number
is moved to position . -
In the fourth phase, the number
is moved to position . -
And so on...
In other words, when the number of the phase is odd, Frane will choose the smallest number not yet chosen, and move it to its final position. In even phases he chooses the largest number not yet chosen. Write a program which, given the initial array, output the number of swaps in each phase of the algorithm.
Input
The first line contains an integer
Output
For each of the
Sample Input 1 | Sample Output 1 |
---|---|
3 2 1 3 |
1 0 0 |
Sample Input 2 | Sample Output 2 |
---|---|
5 5 4 3 2 1 |
4 3 2 1 0 |
Sample Input 3 | Sample Output 3 |
---|---|
7 5 4 3 7 1 2 6 |
4 2 3 0 2 1 0 |