AT_arc069_c [ARC069E] Frequency

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