Selection Sort Movement Distance

Interview

Time limit5sMemory limit1024 MB

Summary

Given a permutation, run selection sort and report the total distance each value moves across all swaps.

Level: Easy3 of 10
Topics: Array, Simulation
Solved: No attempts yet

Problem

A sequence $A$ of length $N$ contains each integer from 1 to $N$ exactly once. Apply the selection sort algorithm to $A$ and find the moving distance of each number.

If you are not familiar with selection sort, read the description below.

Selection sort sorts a sequence $A=\{A_1,A_2,\cdots,A_N\}$ $A = {A_{1}, A_{2}, \dots, A_{N}}$ in ascending order by repeating the following operation $N-1$ $N - 1$ times.
1. In the $i$ -th operation, find the minimum $A_j$ among $A_i,A_{i+1},\cdots,A_N$ .
2. Swap the positions of $A_i$ and $A_j$ . The moving distances of $A_i$ and $A_j$ each increase by $(j-i)$ .

For example, take $\{1,3,5,2,4\}$ . Initially every number has moving distance 0. The algorithm runs as follows.

Swap $A_1=1$ with itself, giving $\{1,3,5,2,4\}$ . The moving distance of 1 increases by 0.
Swap $A_2=3$ with $A_4=2$ , giving $\{1,2,5,3,4\}$ . The moving distances of 2 and 3 each increase by 2.
Swap $A_3=5$ with $A_4=3$ , giving $\{1,2,3,5,4\}$ . The moving distances of 3 and 5 each increase by 1.
Swap $A_4=5$ with $A_5=4$ , giving $\{1,2,3,4,5\}$ . The moving distances of 4 and 5 each increase by 1.

So 1 moves 0, 2 moves 2, 3 moves 3, 4 moves 1, and 5 moves 2.

Input

The first line contains the length $N$ of the sequence.

The second line contains the elements $A_1,A_2,\cdots,A_N$ of the sequence, separated by spaces, in order.

Output

Print $N$ integers separated by spaces on the first line. The $i$ -th integer is the moving distance of $i$ .

Constraints

$1\leq N\leq 5\times 10^5$
Each integer from $1$ to $N$ appears exactly once in $A$ .

Examples2

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