题目描述

Snuke喜欢构建整数序列。

有$N$堆石头，从$1$到$N$进行编号。第$i$堆的石头数量为$a_i$。

Snuke将构建一个长度为$Σa_i$的整数序列$s$，具体步骤如下：

1. 在剩余石头最多的堆中，选择索引最小的堆，将其编号$x$添加到$s$的末尾。
2. 从剩余石头数大于等于$1$的堆中选择一堆，取出一块石头。
3. 如果还存在剩余石头的堆，则返回到步骤1。否则，终止过程。

我们感兴趣的是能够构建的字典序最小的序列。对于$1,2,3,...,N$这些整数，它们在字典序最小的序列中出现了多少次？

约束条件

• $1 \leq N \leq 10^{5}$
• $1 \leq a_i \leq 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