A strong nation relies on strong communication!

Let us return to the era of war and feel the charm of communication.

In a battle on the front line, the enemy has a total of $n$ camps, numbered from $1$ to $n$. The cunning enemy uses telegrams to transmit information from the rear to the front. To ensure the information is delivered, the $i$-th camp will send a telegram to all camps in the range $[i+1, \min(i+r_i, n)]$.

Now, you are a signal soldier equipped with an interceptor. You can sneak into the enemy's formation and place it in one of the enemy's camps. If a telegram is sent from camp $p$ to camp $q$, and the interceptor is placed at $x$ such that $p \le x \le q$, then the telegram will be intercepted. The interception value is $\min(x-p, q-x)$. For each camp $i$, what is the sum of the interception values if the interceptor is placed at camp $i$?

Input

The first line contains an integer $n$ ($2 \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $r_i$ ($1 \le r_i \le n$), separated by spaces.

Output

Output $n$ lines, where the $i$-th line contains the sum of the interception values if the interceptor is placed at camp $i$.

Examples

Input 1

6
4 4 3 2 2 3

Output 1

0
3
6
6
3
0

Note

For the second camp in the example, the sum of the interception values is $2+1=3$. The rest are omitted.