CEOI '19 Practice P2 - Separator

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.65s
Memory limit: 512M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 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_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 equals is described in the problem statement.

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


Comments

There are no comments at the moment.