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}) \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~.

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 1\,000~.

Subtask ~3~ (~40~ points): ~n \le 100\,000~.

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