[USACO20OPEN]Haircut G

题目描述

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$ 时他的头发的不良度。 ----- (有趣的事实:人类平均确实有大约 $10^5$ 根头发!)

输入输出格式

输入格式


输入的第一行包含 $N$。 第二行包含 $A_1,A_2,\ldots,A_N$。

输出格式


对于每一个 $j=0,1,\ldots,N-1$,用一行输出 Farmer John 头发的不良度。 ----- **注意这个问题涉及到的整数大小可能需要使用 $64$ 位整数型存储(例如,C/C++ 中的“long long”)。**

输入输出样例

输入样例 #1

5
5 2 3 3 0

输出样例 #1

0
4
4
5
7

说明

#### 样例解释: 输出的第四行描述了 Farmer John 的头发长度减少到 $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$。 共 $13$ 个测试点,其中 $1$ 为样例,其余性质如下: 测试点 $2$ 满足 $N\le 100$。 测试点 $3\sim 5$ 满足 $N\le 5000$。 测试点 $6\sim 13$ 没有额外限制。 ----- 出题人:Dhruv Rohatgi