题目描述

すぬけ君喜欢制作数列。

现在有 $1$ 到 $N$ 编号的 $N$ 堆石子。第 $i$ 堆有 $a_i$ 个石子。

すぬけ君准备用以下操作，构造一个长度为 $\sum a_i$ 的数列 $s$：

1. 在所有石子数量最多的石堆中，选择编号最小的一个，记其编号为 $x$，然后在 $s$ 的末尾添加 $x$。
2. 任选一个仍有至少 $1$ 个石子的石堆，从中取出一个石子。
3. 如果仍存在至少 $1$ 个石子的石堆，转至步骤 1，否则流程结束。

请你求出：当 $s$ 是按字典序最小的情况下，$s$ 中每个 $1,2,\ldots,N$ 分别出现了多少次。

输入格式

输入一行，包括 $N\ a_1\ a_2\ \ldots\ a_N$。

输出格式

输出 $N$ 行，第 $i$ 行输出 $i$ 在字典序最小的 $s$ 中出现的次数。

样例 1

输入

2
1 2

输出

2
1

样例 2

输入

10
1 2 1 3 2 4 2 5 8 1

输出

10
7
0
4
0
3
0
2
3
0

说明/提示

限制条件

• $1 \leq N \leq 10^{5}$
• $1 \leq a_i \leq 10^{9}$

样例解释 1

可以按如下方式构造出字典序最小的数列：

• 首先最大石堆是第 $2$ 堆，所以把 $2$ 加入 $s$，然后从第 $2$ 堆取走 $1$ 个石子。
• 然后最大石堆为第 $1$ 堆和第 $2$ 堆。选择编号较小的第 $1$ 堆，把 $1$ 加入 $s$，然后再从第 $2$ 堆取走 $1$ 个石子。
• 然后最大石堆只有第 $1$ 堆，把 $1$ 加入 $s$，再从第 $1$ 堆取走 $1$ 个石子。

此时构造出的数列为 $(2,1,1)$。其中 $1$ 出现 $2$ 次，$2$ 出现 $1$ 次。

由 ChatGPT 5 翻译