問題文

$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}\] の転倒数を求めてください。

転倒数とは 数列 A = \[a_0, a_1, a_2, \\dots, a_{N-1}\] の転倒数とは、$i < j$ かつ $a_i > a_j$ を満たす添字の組 $(i, j)$ の個数のことです。

制約

• 入力は全て整数
• $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