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
Comments
Data were updated post-contest to break some unintended solutions.
:^)