配点 : $700$ 点

問題文

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

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

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

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

$s$ が辞書順で最小の数列となるようにしたとき、$s$ に $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$ 行目では辞書順で最小の $s$ における $i$ の出現回数を出力せよ。

2
1 2

2
1

以下の手順で辞書順最小であるような数列が構成できます。

• 石の数が最大であるような山は $2$ 番なので $2$ を $s$ に追加する。その後、番号 $2$ の山から石を $1$ つ取り除く。
• 石の数が最大であるような山は $1$ 番と $2$ 番なので、最も番号が小さい $1$ を $s$ に追加する。その後、番号 $2$ の山から石を $1$ つ取り除く。
• 石の数が最大であるような山は $1$ 番なので $1$ を $s$ に追加する。その後、番号 $1$ の山から石を $1$ つ取り除く。

このときできる数列は $(2,1,1)$ となります。$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