题目描述

给定一个序列 A = \[a_0, a_1, a_2, \dots, a_{N-1}\]，它是 $0, 1, 2, \dots, N - 1$ 的一个排列。
对于每个 $k = 0, 1, 2, \dots, N - 1$，找出序列 B = \[b_0, b_1, b_2, \dots, b_{N-1}\] 的逆序数，其中 $b_i = a_{i+k \bmod N}$。

什么是逆序数？对于序列 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