Score : $500$ points

故事

有一个长水槽，上面放置着不同高度的木板，木板间隔相等。高桥想知道当水从水槽的一端倒入时，水到达木板分隔的每个部分的时间。

以上为大语言模型 kimi 翻译，仅供参考。

Story

There is a long water tank with boards of different heights placed at equal intervals. Takahashi wants to know the time at which water reaches each section separated by the boards when water is poured from one end of the tank.

Problem Statement

You are given a sequence of positive integers of length $N$: $H=(H _ 1,H _ 2,\dotsc,H _ N)$.

There is a sequence of non-negative integers of length $N+1$: $A=(A _ 0,A _ 1,\dotsc,A _ N)$. Initially, $A _ 0=A _ 1=\dotsb=A _ N=0$.

Perform the following operations repeatedly on $A$:

1. Increase the value of $A _ 0$ by $1$.
2. For $i=1,2,\ldots,N$ in this order, perform the following operation:
   • If $A _ {i-1}\gt A _ i$ and $A _ {i-1}\gt H _ i$, decrease the value of $A _ {i-1}$ by 1 and increase the value of $A _ i$ by $1$.

For each $i=1,2,\ldots,N$, find the number of operations before $A _ i>0$ holds for the first time.

Constraints

• $1\leq N\leq2\times10 ^ 5$
• $1\leq H _ i\leq10 ^ 9\ (1\leq i\leq N)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$

$H _ 1$ $H _ 2$ $\dotsc$ $H _ N$

Output

Print the answers for $i=1,2,\ldots,N$ in a single line, separated by spaces.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

4 5 13 14 26

The first five operations go as follows.

Here, each row corresponds to one operation, with the leftmost column representing step 1 and the others representing step 2.

From this diagram, $A _ 1\gt0$ holds for the first time after the 4th operation, and $A _ 2\gt0$ holds for the first time after the 5th operation.

Similarly, the answers for $A _ 3, A _ 4, A _ 5$ are $13, 14, 26$, respectively.

Therefore, you should print 4 5 13 14 26.

Sample Input 2

6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 2

1000000001 2000000001 3000000001 4000000001 5000000001 6000000001

Note that the values to be output may not fit within a $32$-bit integer.

Sample Input 3

15
748 169 586 329 972 529 432 519 408 587 138 249 656 114 632

Sample Output 3

749 918 1921 2250 4861 5390 5822 6428 6836 7796 7934 8294 10109 10223 11373