Turbo Sort

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.

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.

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