Problem Statement

Given is $a sequence A = [a_0, a_1, a_2, \dots, a_{N-1}]$ that is a permutation of $0, 1, 2, \dots, N - 1$.
For each $k = 0, 1, 2, \dots, N - 1,$ find the inversion number of the sequence $B = [b_0, b_1, b_2, \dots, b_{N-1}]$ defined as $b_i = a_{i+k \bmod N}$.

What is inversion number?
The inversion number of $a sequence A = [a_0, a_1, a_2, \dots, a_{N-1}]$ is the number of pairs of indices (i, j) such that i < j and a_i > a_j.

Input

Input is given from Standard Input in the following format:
N
$a_0 a_1 a_2 \cdots a_{N-1}$

Output

Print N lines.
The (i + 1)-th line should contain the answer for the case k = i.

Constraints

• All values in input are integers.
• 2 ≤ N ≤ $3 \times 10^5$
• $a_0, a_1, a_2, \dots, a_{N-1}$ is a permutation of $0, 1, 2, \dots, N - 1$.

Sample Input 1

4
0 1 2 3

Sample Output 1

0
3
4
3

We have A = [0, 1, 2, 3].
For k = 0, the inversion number of B = [0, 1, 2, 3] is 0.
For k = 1, the inversion number of B = [1, 2, 3, 0] is 3.
For k = 2, the inversion number of B = [2, 3, 0, 1] is 4.
For k = 3, the inversion number of B = [3, 0, 1, 2] is 3.

Sample Input 2

10
0 3 1 5 4 2 9 6 8 7

Sample Output 2

9
18
21
28
27
28
33
24
21
14

见题面 Input 部分

见题面 Output 部分