haircut.cpp/in/out/1s/256M

李明对整理自己的头发感到疲惫，于是他决定去理发。他有一排\(N\)缕头发，第\(i\)缕头发初始时长度为\(A_i\)微米\((0≤ A_i ≤N)\)。理想情况下，他想要他的头发在长度上单调递增，所以他定义他的头发的“不良度”为逆序对的数量：满足\(i<j\)及\(A_i>A_j\)的二元对\((i,j)\)。

对于每一个\(j=0,1,…,N−1\)，李明想要知道他所有长度大于\(j\)的头发的长度均减少到\(j\)时他的头发的不良度。

【输入描述】

输入的第一行包含\(N\)。
第二行包含\(A_1,A_2,…,A_N\)。

【输出描述】

对于每一个\(j=0,1,…,N−1\)，用一行输出李明头发的不良度。

【样例】

haircut.in

5
5 2 3 3 0

haircut.out

0
4
4
5
7

【样例解释】

输出的第四行描述了 李明 的头发长度减少到 3 时的逆序对数量。
\(A=[3,2,3,3,0]\) 有五个逆序对：\(A_1>A_2\), \(A_1>A_5\), \(A_2>A_5\), \(A_3>A_5\) 和 \(A_4>A_5\)。

【数据范围】

对于 100%的数据， 1≤N≤10^5。
共 13 个测试点，其中 1 为样例，其余性质如下：
测试点 2 满足 N≤100。
测试点 3∼5 满足 N≤5000。
测试点 6∼13 没有额外限制。