Let $A=(a_1,a_2,\dots )$ be a sequence of distinct integers. An index $j$ is called a separator if the following two conditions hold:

• for all $k<j:a_k<a_j$,
• for all $k>j:a_k>a_j$.

In other words, the array $A$ consists of three parts: all elements smaller than $a_j$, then $a_j$ itself, and finally all elements greater than $a_j$.

For instance, let $A=(30,10,20,50,80,60,90)$. The separators are the indices $4$ and $7$, corresponding to the values $50$ and $90$.

The sequence $A$ is initially empty. You are given a sequence $a_1,\dots ,a_n$ of elements to append to $A$, one after another. After appending each $a_i$, output the current number $s_i$ of separators in the sequence you have.

The input format is selected so that you have to compute the answers online. Instead of the elements $a_i$ you should append to $A$, you are given a sequence $b_i$.

Process the input as follows:

The empty sequence $A$ contains $s_0=0$ separators.

For each $i$ from $1$ to $n$, inclusive:

1. Calculate the value $a_i=(b_i+s_{i-1})mod{10}^9$.
2. Append $a_i$ to the sequence $A$.
3. Calculate $s_i$: the number of separators in the current sequence $A$.
4. Output a line containing the value $s_i$.

Input

The first line contains a single integer $n$ $(1\le n\le {10}^6)$: the number of queries to process.

Then, $n$ lines follow. The $i$-th of these lines contains the integer $b_i$ $(0\le b_i\le {10}^9-1)$. The values $b_i$ are chosen in such a way that the values $a_i$ you'll compute will all be distinct.

Output

As described above, output $n$ lines with the values $s_1$ through $s_n$.

Scoring

Subtask $1$ ($20$ points): $n\le 100$.

Subtask $2$ ($30$ points): $n\le 1000$.

Subtask $3$ ($40$ points): $n\le 100000$.

Subtask $4$ ($10$ points): no additional constraints.

Sample Input 1

7
30
9
20
50
79
58
89

Sample Output 1

1
0
0
1
2
1
2

Sample Input 2

10
0
0
0
0
0
0
0
0
0
0

Sample Output 2

1
2
3
4
5
6
7
8
9
10

Note

The first example is described in the problem statement.

The second example is decoded as $A=(0,1,2,3,4,5,6,7,8,9)$.