Alice is training for an upcoming javelin-throwing competition! The javelin-throwing field can be modelled as a 1-D line, with Alice standing at the coordinate ~0~.

Alice throws ~N~ javelins in the positive direction. When she throws a javelin, it lands at some real-valued point on the field, making a hole there. It's possible for the javelin to land exactly in a previously made hole, in which case no new hole is made. Holes are permanent, and there are initially no holes in the field.

Right after the ~i^\text{th}~ throw, Alice counts ~a_i~ and ~b_i~, the number of holes strictly behind and strictly in front of the javelin she just threw (respectively). She then tells you ~a_i~. You don't know anything else about her throws.

Given the information you have right after the ~i^\text{th}~ throw, what is the minimum possible value of ~\sum_{j=1}^i b_j~?

Constraints

~0 \le a_i < i~

Subtask 1 [15%]

~1 \le N \le 5000~

Subtask 2 [85%]

~1 \le N \le 2 \times 10^6~

Input Specification

The first line contains an integer ~N~, the number of throws.

The second line contains ~N~ space-separated integers, ~a_1, a_2, \dots, a_N~.

Output Specification

Output ~N~ space-separated integers. The ~i^\text{th}~ integer should be the minimum possible value of ~\sum_{j=1}^i b_j~, given that you know ~a_1~ through ~a_i~.

Sample Input 1

3
0 0 2

Sample Output 1

0 0 1

Explanation for Sample 1

There are no holes in front of throw ~1~:

So the first answer is ~0~.

On throw ~2~, you know that ~a_1 = a_2 = 0~. It's possible that both throws landed at exactly the same point, in which case there would be no holes in front of either throw:

So the second answer is ~0 + 0 = 0~.

However, you then learn that there were ~2~ holes behind throw ~3~. So the second throw must have landed behind the first, and the only solution would be

for an answer of ~0 + 1 + 0 = 1~.

Sample Input 2

6
0 1 0 3 0 2

Sample Output 2

0 0 1 2 5 6

Sample Input 3

5
0 1 2 1 2

Sample Output 3

0 0 0 1 1