COCI 2007/2008, Contest #2

Task TURBO

Frane has been given the task of sorting an array of numbers. The array consists of N integers, each between 1 and N (inclusive), with each of those appearing exactly once in the array. Frane has come up with the following sorting algorithm which operates in N phases, and named it turbosort:

• In the first phase, the number 1 is moved to position 1 by repeatedly swapping consecutive elements.
• In the second phase, the number N is moved to position N in the same manner.
• In the third phase, the number 2 is moved to position 2.
• In the fourth phase, the number N−1 is moved to position N−1.
• 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 N (1 ≤ N ≤ 100 000), the number of elements in the array.

Each of the following N lines contains an integer between 1 and N (inclusive), the array to be sorted. The array will contain no duplicates.

Output

For each of the N phases, output the number of swaps on a single line.

Scoring

In test cases worth 70% of points, N will be less than 100.

Examples

3
2
1
3

1
0
0

5
5
4
3
2
1

4
3
2
1
0

7
5
4
3
7
1
2
6

4
2
3
0
2
1
0

All Submissions
Best Solutions

Point Value: 15
Time Limit: 1.00s
Memory Limit: 32M
Added: Aug 13, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)