You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC190F] Shift and Inversions

题面翻译

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

或者这么说，一个数组$A$，$A$中元素的下标是$0,1,...,n-1$，$A$中元素恰好也是$0,1,...,n-1$各一个。现在定义数组$B_k$，它的第$i$个元素为$a_{i+k \mod n}$。问对$k=0,1,...,n-1$，$B_k$的逆序对数量是多少。

输入格式

第一行一个整数$n$，第二行$n$个整数$a_i$，保证数组是$0,1,...,n-1$的一个排列。

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

输出格式

输出$n$行，第$i$行表示$B_{i-1}$的逆序对数量。

样例 #1

样例输入 #1

4
0 1 2 3

样例输出 #1

0
3
4
3

样例 #2

样例输入 #2

10
0 3 1 5 4 2 9 6 8 7

样例输出 #2

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$ 的一个全排列