17638번 - Separator 서브태스크스페셜 저지다국어

문제

Let A = (a₁, a₂, . . .) 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 then 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₁, . . . , 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 s0 = 0 separators.

For each i from 1 to n, inclusive:

1. Calculate the value a_i = (b_i + s_i−1) mod 10⁹.
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 ≤ n ≤ 10⁶): the number of queries to process.

Then, n lines follow. The i-th of these lines contains the integer b_i (0 ≤ b_i ≤ 10⁹ − 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₁ through s_n.

제한

서브태스크

힌트

The first example equals is described in the problem statement.

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