F - Shift and Inversions /

問題文

0, 1, 2, \dots, N - 1 を並び替えた数列 A = [a_0, a_1, a_2, \dots, a_{N-1}] が与えられます。
k = 0, 1, 2, \dots, N - 1 のそれぞれについて、b_i = a_{i+k \bmod N} で定義される数列 B = [b_0, b_1, b_2, \dots, b_{N-1}] の転倒数を求めてください。

制約

• 入力は全て整数
• 2 ≤ N ≤ 3 \times 10^5
• a_0, a_1, a_2, \dots, a_{N-1}0, 1, 2, \dots, N - 1 の並び替えである

入力

N
a_0 a_1 a_2 \cdots a_{N-1}


出力

N 行出力せよ。
i + 1 行目には、k = i としたときの答えを出力せよ。

入力例 1

4
0 1 2 3


出力例 1

0
3
4
3


A = [0, 1, 2, 3] です。

k = 0 のとき、B = [0, 1, 2, 3] の転倒数は 0 です。
k = 1 のとき、B = [1, 2, 3, 0] の転倒数は 3 です。
k = 2 のとき、B = [2, 3, 0, 1] の転倒数は 4 です。
k = 3 のとき、B = [3, 0, 1, 2] の転倒数は 3 です。

入力例 2

10
0 3 1 5 4 2 9 6 8 7


出力例 2

9
18
21
28
27
28
33
24
21
14


Score : 600 points

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.

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.

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.

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