Turbo Sort

Time limit1sMemory limit128 MB

Summary

Simulate a bubble-sort-like process that alternately moves the smallest and largest remaining values to the boundary, printing swap counts needed at each of N steps efficiently.

Level: Medium6 of 10
Topics: Binary search, Implementation, Simulation, Math
Solved: No attempts yet

Problem

Turbo sort is a sorting process that can be applied only to an array containing each integer from 1 through N exactly once.

The process has N steps. Think of only the numbers that have not been selected yet as remaining.

On an odd-numbered step, choose the smallest remaining number. Swap it with adjacent numbers until it reaches the leftmost still-undecided position.
On an even-numbered step, choose the largest remaining number. Swap it with adjacent numbers until it reaches the rightmost still-undecided position.

For each step, determine how many adjacent swaps are actually needed.

Given an array made of the numbers from 1 through N, print the number of adjacent swaps performed at each step of turbo sort.

Input

The first line contains N, the size of the array. N is a natural number between 1 and 100,000 inclusive.

Each of the next N lines contains one number in the array, in order from front to back. Every number is between 1 and N inclusive, and no number appears more than once.

Output

Print N lines. On the i-th line, print the number of adjacent swaps needed during the i-th step of turbo sort.

Examples3

Example 1
Input
```
3
2
1
3
```
Expected output
```
1
0
0
```
Example 2
Input
```
5
5
4
3
2
1
```
Expected output
```
4
3
2
1
0
```
Example 3
Input
```
7
5
4
3
7
1
2
6
```
Expected output
```
4
2
3
0
2
1
0
```