P6339 [COCI 2007/2008 #2] TURBO

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.

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

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

#### 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](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #2](https://hsin.hr/coci/archive/2007_2008/contest2_tasks.pdf) *T4 TURBO***。 Translated by ChatGPT 5