Contest Duration: - (local time) (100 minutes) Back to Home
F - Shift and Inversions /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

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