Staged Adjacent Swap Sorting

You are given a permutation of the numbers \(1\) through \(n\) of length \(n\). Your task is to sort the permutation in ascending order by performing a sequence of adjacent swaps in multiple stages.

The sorting procedure is divided into stages as follows:

1. In the first stage, move the number \(1\) to the first position (index 1) by repeatedly swapping it with an adjacent element.
2. In the second stage, move the number \(n\) to the last position (index \(n\)) by the same method.
3. In the third stage, move the number \(2\) to the second position.
4. In the fourth stage, move the number \(n-1\) to the \(n-1\)th position.
5. Continue in this alternating fashion until every number is moved to its correct sorted position.

For each stage, output the number of adjacent swaps performed.

Note: Throughout the process, the array is modified by the swaps made in earlier stages.

inputFormat

The input consists of two lines.

1. The first line contains an integer \(n\) (\(1 \le n \le 10^5\)) representing the size of the permutation.
2. The second line contains \(n\) space-separated integers representing a permutation of \(1\) through \(n\).

outputFormat

For each stage in the process, print a line containing a single integer which represents the number of adjacent swaps performed in that stage.

sample

4
1 3 4 2

0
1
1
0