/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 700 点
問題文
すぬけくんは数列を作るのが好きです。
1 から N までの番号がついた石の山があります。 i 番の石の山は a_i 個の石からなります。
すぬけくんは以下の手順により長さ Σa_i の数列 s を構成することにしました。
- 石の数が最大である山のうち、最も番号が小さい山の番号を x として、s の末尾に x を追加する
- 石が 1 個以上存在する山を 1 つ選んで、選んだ山から石を 1 つ取り除く
- 石が 1 個以上存在する山が存在するなら 1. へ、そうでなければ数列の構成を終了する
s が辞書順で最小の数列となるようにしたとき、s に 1,2,3,...,N という数がそれぞれいくつ含まれるか求めなさい。
制約
- 1 ≦ N ≦ 10^{5}
- 1 ≦ a_i ≦ 10^{9}
入力
入力は以下の形式で標準入力から与えられる。
N
a_1 a_2 ... a_{N}
出力
答えを N 行に出力せよ。i 行目では辞書順で最小の s における i の出現回数を出力せよ。
入力例 1
2 1 2
出力例 1
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 つ含まれます。
入力例 2
10 1 2 1 3 2 4 2 5 8 1
出力例 2
10 7 0 4 0 3 0 2 3 0
Score : 700 points
Problem Statement
Snuke loves constructing integer sequences.
There are N piles of stones, numbered 1 through N. The pile numbered i consists of a_i stones.
Snuke will construct an integer sequence s of length Σa_i, as follows:
- Among the piles with the largest number of stones remaining, let x be the index of the pile with the smallest index. Append x to the end of s.
- Select a pile with one or more stones remaining, and remove a stone from that pile.
- If there is a pile with one or more stones remaining, go back to step 1. Otherwise, terminate the process.
We are interested in the lexicographically smallest sequence that can be constructed. For each of the integers 1,2,3,...,N, how many times does it occur in the lexicographically smallest sequence?
Constraints
- 1 ≤ N ≤ 10^{5}
- 1 ≤ a_i ≤ 10^{9}
Input
The input is given from Standard Input in the following format:
N
a_1 a_2 ... a_{N}
Output
Print N lines. The i-th line should contain the number of the occurrences of the integer i in the lexicographically smallest sequence that can be constructed.
Sample Input 1
2 1 2
Sample Output 1
2 1
The lexicographically smallest sequence is constructed as follows:
- Since the pile with the largest number of stones remaining is pile 2, append 2 to the end of s. Then, remove a stone from pile 2.
- Since the piles with the largest number of stones remaining are pile 1 and 2, append 1 to the end of s (we take the smallest index). Then, remove a stone from pile 2.
- Since the pile with the largest number of stones remaining is pile 1, append 1 to the end of s. Then, remove a stone from pile 1.
The resulting sequence is (2,1,1). In this sequence, 1 occurs twice, and 2 occurs once.
Sample Input 2
10 1 2 1 3 2 4 2 5 8 1
Sample Output 2
10 7 0 4 0 3 0 2 3 0