说明

时间限制：1 Sec 内存限制：256 MB 输入文件：program.in 输出文件：program.out

小明发现了一个长度为 $N$ 的数列 $A = (A_0, A_1, A_2, \dots, A_{N-1})$。

他有一个针对长度为 $N$ 的数列 $v$ 的程序如下：

cnt = 0
for i = 0 to N-1
    for j = 0 to N-2
        if v[j] > v[j+1]
            交换 v[j] 和 v[j+1]
            cnt 加 1

小明需要对于 $k=0,1,\ldots,N-1$ 得到的序列 $v_k= (A_{k \ mod \ N}, A_{(k + 1) \ mod \ N}, A_{(k + 2) \ mod \ N}, \dots, A_{(k + N - 1) \ mod \ N})$ 执行该程序对应的最终 $cnt$ 值。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行一个整数，依次为 $A_0,A_1,A_2,\ldots,A_{N-1}$。

输出格式

输出 $N$ 行，第 $i+1$ 行一个整数，表示对于序列 $v_i=(A_{k \ mod \ N}, A_{(k + 1) \ mod \ N}, A_{(k + 2) \ mod \ N}, \dots, A_{(k + N - 1) \ mod \ N})$ 执行该程序得到的最终的 $cnt$ 值。

样例

样例 1

5
2
5
1
4
3

5
7
3
7
5

样例说明：

例如，对数列 $(2, 5, 1, 4, 3)$ 执行该程序时，数列会按以下方式变化：

$(2, 5, 1, 4, 3) → (2, 1, 5, 4, 3) → (2, 1, 4, 5, 3) → (2, 1, 4, 3, 5) → (1, 2, 4, 3, 5) → (1, 2, 3, 4, 5)$

由于过程中共发生了 $5$ 次交换，因此最终的 $cnt$ 值为 $5$。

数据范围

对于 10% 的数据，$N \le 10$；

对于 40% 的数据，$N \le 500$；

对于 100% 的数据，$1 \le N \le 500000$，$1 \le A_i \le 10^9$。