题目描述

すぬけくんは数列を作るのが好きです。

$1$ から $N$ までの番号がついた石の山があります。 $i$ 番の石の山は $a_i$ 個の石からなります。

すぬけくんは以下の手順により長さ $Σa_i$ の数列 $s$ を構成することにしました。

1. 石の数が最大である山のうち、最も番号が小さい山の番号を $x$ として、$s$ の末尾に $x$ を追加する
2. 石が $1$ 個以上存在する山を $1$ つ選んで、選んだ山から石を $1$ つ取り除く
3. 石が $1$ 個以上存在する山が存在するなら $1.$ へ、そうでなければ数列の構成を終了する

$s$ が辞書順で最小の数列となるようにしたとき、$s$ に $1,2,3,...,N$ という数がそれぞれいくつ含まれるか求めなさい。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $a_1$ $a_2$ $...$ $a_{N}$

输出格式

答えを $N$ 行に出力せよ。$i$ 行目では辞書順で最小の $s$ における $i$ の出現回数を出力せよ。

题目大意

给定 $N$ 堆石子，第 $i$ 堆大小为 $A_i$。

现在你需要构造一个长度 $\sum A_i$ 的序列 $S$，构造流程如下：

• 找到当前石子数量最多的那堆石子，如果有多个则取最前面哪个，将下标记作 $P$，将 $P$ 写在 $S$ 末尾。

• 选择一堆石子，拿一个石子出来。

• 如果还有石子剩余，重复这个流程。

现在需要你最小化 $S$ 的字典序，输出 $1 \sim n$ 在 $S$ 中出现了多少次。

2
1 2

2
1

10
1 2 1 3 2 4 2 5 8 1

10
7
0
4
0
3
0
2
3
0

提示

制約

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

Sample Explanation 1

以下の手順で辞書順最小であるような数列が構成できます。 - 石の数が最大であるような山は $2$ 番なので $2$ を $s$ に追加する。その後、番号 $2$ の山から石を $1$ つ取り除く。 - 石の数が最大であるような山は $1$ 番と $2$ 番なので、最も番号が小さい $1$ を $s$ に追加する。その後、番号 $2$ の山から石を $1$ つ取り除く。 - 石の数が最大であるような山は $1$ 番なので $1$ を $s$ に追加する。その後、番号 $1$ の山から石を $1$ つ取り除く。 このときできる数列は $(2,1,1)$ となります。$1$ は $2$ つ含まれ、$2$ は $1$ つ含まれます。