Separator

Let $A = (a_1, a_2, \ldots)$ 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, \ldots, 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}) \bmod 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$.

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.

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

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)$.