题目描述

Farmer John 要经常对他养殖的奶牛的毛发进行裁剪。奶牛有一排 $N$ 缕头发，第 $i$ 缕头发初始时长度为 $A_i$ 微米（$0\le A_i\le N$）。理想情况下，他想要奶牛的毛发在长度上单调不降，所以他定义奶牛毛发的“不良度”为逆序对的数量：满足 $i < j$ 及 $A_i > A_j$ 的二元对 $(i,j)$。

对于每一个 $j=0,1,\ldots,N-1$，Farmer John 想要知道奶牛所有长度大于 $j$ 的毛发的长度均减少到 $j$ 时，奶牛毛发的不良度是多少。

输入格式

输入的第一行包含 $N$。

第二行包含 $A_1,A_2,\ldots,A_N$。

输出格式

对于每一个 $j=0,1,\ldots,N-1$，用一行输出奶牛毛发的不良度。

输入输出样例 #1

输入 #1

5
5 2 3 3 0

输出 #1

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\le N\le 10^5$。

测试点 $2$ 满足 $N\le 100$。

测试点 $3\sim 5$ 满足 $N\le 5000$。

测试点 $6\sim 13$ 没有额外限制。

时限：2s

空间：256MB