← 返回题目列表

AtCoder · arc069_c

E. 频率

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

Snuke 喜欢构造整数序列。

有 N 一堆石头,已编号 1 通过 N。 堆编号 i 包括 a_i 石头。

Snuke 将构造一个整数序列 s 长度 Σa_i,如下:

  1. 在剩余石子数量最多的堆中,令 x 是索引最小的堆的索引。追加 x 到年底 s.
  2. 选择一堆剩余一颗或多颗石子,然后从该堆中移走一颗石子。
  3. 如果一堆石子剩余一个或多个,则返回步骤 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