移位与逆序对

题目描述

给定一个由 $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 \lt j$ 且 $a_i \gt a_j$ 的下标对 $(i, j)$ 的个数。

输入格式

输入按以下格式从标准输入给出：

$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

数据范围

• 输入均为整数
• $2 \le N \le 3 \times 10^5$
• $a_0, a_1, a_2, \dots, a_{N-1}$ 是 $0, 1, 2, \dots, N - 1$ 的一个排列