Problem Description

Given a permutation of length $n$ containing $1 \sim n$, you need to sort it in increasing order. The sorting rules are as follows:

• Phase 1: Move the number $1$ to index $1$ by swapping it with adjacent numbers.
• Phase 2: Move the number $n$ to index $n$ in the same way.
• Phase 3: Move the number $2$ to index $2$ in the same way.
• Phase 4: Move the number $n-1$ to index $n-1$ in the same way.

And so on.

For each phase, output the number of swaps.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain one integer, describing a permutation of $1 \sim n$.

Output Format

Output a total of $n$ lines. For each phase, output the number of swaps.

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

Hint

Constraints

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

Notes

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

Translated by ChatGPT 5