[ARC069E] Frequency

题意翻译

给定 $N$ 堆石子,第 $i$ 堆大小为 $A_i$。 现在你需要构造一个长度 $\sum A_i$ 的序列 $S$,构造流程如下: * 找到当前石子数量最多的那堆石子,如果有多个则取最前面哪个,将下标记作 $P$,将 $P$ 写在 $S$ 末尾。 * 选择一堆石子,拿一个石子出来。 * 如果还有石子剩余,重复这个流程。 现在需要你最小化 $S$ 的字典序,输出 $1 \sim n$ 在 $S$ 中出现了多少次。

题目描述

[problemUrl]: https://atcoder.jp/contests/arc069/tasks/arc069_c すぬけくんは数列を作るのが好きです。 $ 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 $ の出現回数を出力せよ。

输入输出样例

输入样例 #1

2
1 2

输出样例 #1

2
1

输入样例 #2

10
1 2 1 3 2 4 2 5 8 1

输出样例 #2

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 $ つ含まれます。