题目描述

$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\ かつ\ a_i\ >\ a_j$ を満たす添字の組 $(i,\ j)$ の個数のことです。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

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

题目大意

$n$ 个 $0$ 到 $n$ $-$ $1$ 全排列的数组，然后这个数组会循环左移 $n$ $-$ $1$, 求这个过程中数组的逆序数对是多少？

4
0 1 2 3

0
3
4
3

10
0 3 1 5 4 2 9 6 8 7

9
18
21
28
27
28
33
24
21
14

提示

制約

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

Sample Explanation 1

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