配点 : $600$ 点

問題文

$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 \leq N \leq 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$ としたときの答えを出力せよ。

4
0 1 2 3

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$ です。

10
0 3 1 5 4 2 9 6 8 7

9
18
21
28
27
28
33
24
21
14