Problem Description

Given a permutation of length $n$ containing numbers from $1$ to $n$, you need to sort it in ascending order following these rules:

• In the first phase, move the number $1$ to the index $1$ by swapping it with adjacent numbers.
• In the second phase, move the number $n$ to the index $n$ using the same method.
• In the third phase, move the number $2$ to the index $2$ using the same method.
• In the fourth phase, move the number $n-1$ to the index $n-1$ using the same method.

This process continues alternately.

For each phase, output the number of swaps made.

Input Format

The first line of input contains an integer $n$.

The next $n$ lines each contain an integer, describing a permutation of numbers from $1$ to $n$.

Output Format

The output should consist of $n$ lines, with each line representing the number of swaps made in each phase.

Sample Input and Output

Sample Input #1

3
2
1
3

Sample Output #1

1
0
0

Sample Input #2

5
5
4
3
2
1

Sample Output #2

4
3
2
1
0

Sample Input #3

7
5
4
3
7
1
2
6

Sample Output #3

4
2
3
0
2
1
0

Notes

Data Size and Constraints

• For $70\%$ of the test cases, $n < 100$.
• For $100\%$ of the test cases, $1 \le n \le 10^5$.

This problem is translated from COCI2007-2008 CONTEST #2 T4 TURBO.

见题面 Input 部分

见题面 Output 部分