/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
ある星には N 人の宇宙人がおり、全員未成年です。
i 人目の宇宙人は現在 A_i 個の石を所持しており、ちょうど i 年後に成人します。
この星では誰かが成人するとき、石を 1 個以上所持している成人全員が、成人する宇宙人に成人祝いとして石を 1 個渡します。
N 年後に各宇宙人が所持している石の個数を求めてください。
ただし、今後新たな宇宙人は産まれないものとします。
制約
- 1 \leq N \leq 5 \times 10^5
- 0 \leq A_i \leq 5 \times 10^5
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
N 年後に i 人目の宇宙人が所持している石の個数を B_i として B_1, B_2, \ldots, B_N をこの順に空白区切りで出力せよ。
入力例 1
4 5 0 9 3
出力例 1
2 0 10 5
i 人目の宇宙人が持っている石の個数を C_i で表します。
はじめ (C_1, C_2, C_3, C_4) = (5, 0, 9, 3) です。
1 年後には (C_1, C_2, C_3, C_4) = (5, 0, 9, 3) となります。
2 年後には (C_1, C_2, C_3, C_4) = (4, 1, 9, 3) となります。
3 年後には (C_1, C_2, C_3, C_4) = (3, 0, 11, 3) となります。
4 年後には (C_1, C_2, C_3, C_4) = (2, 0, 10, 5) となります。
入力例 2
5 4 6 7 2 5
出力例 2
0 4 7 4 9
入力例 3
10 2 9 1 2 0 4 6 7 1 5
出力例 3
0 2 0 0 0 4 7 10 4 10
Score : 400 points
Problem Statement
On a certain planet, there are N aliens, all of whom are minors.
The i-th alien currently has A_i stones, and will become an adult exactly i years later.
When someone becomes an adult on this planet, every adult who has at least one stone gives exactly one stone as a congratulatory gift to the alien who has just become an adult.
Find how many stones each alien will have after N years.
Assume that no new aliens will be born in the future.
Constraints
- 1 \leq N \leq 5 \times 10^5
- 0 \leq A_i \leq 5 \times 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Let B_i be the number of stones owned by the i-th alien after N years. Print B_1, B_2, \ldots, B_N in this order, separated by spaces.
Sample Input 1
4 5 0 9 3
Sample Output 1
2 0 10 5
Let C_i be the number of stones that the i-th alien has at a given time.
Initially, (C_1, C_2, C_3, C_4) = (5, 0, 9, 3).
After 1 year, (C_1, C_2, C_3, C_4) = (5, 0, 9, 3).
After 2 years, (C_1, C_2, C_3, C_4) = (4, 1, 9, 3).
After 3 years, (C_1, C_2, C_3, C_4) = (3, 0, 11, 3).
After 4 years, (C_1, C_2, C_3, C_4) = (2, 0, 10, 5).
Sample Input 2
5 4 6 7 2 5
Sample Output 2
0 4 7 4 9
Sample Input 3
10 2 9 1 2 0 4 6 7 1 5
Sample Output 3
0 2 0 0 0 4 7 10 4 10