分数: 700 点
问题陈述
Snuke 喜欢构造整数序列。
有 N 一堆石头,已编号 1 通过 N。 堆编号 i 包括 a_i 石头。
Snuke 将构造一个整数序列 s 长度 Σa_i,如下:
- 在剩余石子数量最多的堆中,令 x 是索引最小的堆的索引。追加 x 到年底 s.
- 选择一堆剩余一颗或多颗石子,然后从该堆中移走一颗石子。
- 如果一堆石子剩余一个或多个,则返回步骤 1。否则,终止该过程。
我们对可以构造的字典顺序最小的序列感兴趣。对于每个整数 1,2,3,...,N,它在字典顺序最小的序列中出现了多少次?
约束
- 1 ≤ N ≤ 10^{5}
- 1 ≤ a_i ≤ 10^{9}
输入
输入由标准输入按以下格式给出:
N
a_1 a_2 ... a_{N}
输出
打印 N 行。的 i- 第行应包含整数出现的次数 i 按字典顺序可以构造的最小序列。
示例输入 1
2 1 2
示例输出 1
2 1
字典顺序最小的序列构造如下:
- 由于剩余石子数量最多的堆是堆 2,追加 2 到年底 s。然后,从堆中取出一块石头 2.
- 由于剩余石子数量最多的堆是堆 1 和 2,追加 1 到年底 s (我们采用最小的索引)。然后,从堆中取出一块石头 2.
- 由于剩余石子数量最多的堆是堆 1,追加 1 到年底 s。然后,从堆中取出一块石头 1.
结果序列是 (2,1,1)。在这个序列中, 1 出现两次,并且 2 出现一次。
示例输入 2
10 1 2 1 3 2 4 2 5 8 1
示例输出 2
10 7 0 4 0 3 0 2 3 0