Sort (sort, 3s, 512M)

大象有一个排序算法：

def incorrect_sort(x):
    for i=1,2...|x|:
        m=i                 # (*)
        for j=1,2...|x|:
            if x[m]>x[j]:
                m=j         # (*)
        swap(x[i],x[m])

这个算法不一定对，但是不重要。你需要计算对于给定 $1$ 到 $n$ 的排列 $a_1,a_2,\cdots,a_n$，每个前缀 $a_1,a_2,\cdots,a_i$ 调用 incorrect_sort 时 $m$ 会被赋值几次（即被标注星号的行的被执行次数）。

输入格式

第一行一个正整数 $n$，表示序列长度。

第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，表示序列元素。

输出格式

输出一行 $n$ 个非负整数，表示对 每个前缀 调用 incorrect_sort 时 $m$ 被赋值的次数。

样例输入1

6
4 5 2 3 6 1

样例输出1

1 3 6 8 13 17

样例输入2

6
5 4 2 6 3 1

样例输出2

1 4 8 11 13 19

样例输入3、样例输出3

见选手文件夹下 ex_sort3.in 和 ex_sort3.ans。500。

样例输入4、样例输出4

见选手文件夹下 ex_sort4.in 和 ex_sort4.ans。500000。

数据范围

对于所有数据，$1\le n\le 500000$，$1\le a_i\le n$，所有 $a_i$ 两两不同。

对于 10% 的数据，$n\le 500$。

对于 40% 的数据，$n\le 4000$​。

对于另外 30% 的数据，保证 $a_1,a_2,\cdots,a_n$ 在所有可能排列中等概率均匀随机。