## CEOI '19 Practice P2 - Separator

View as PDF

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

Problem type

Let be a sequence of distinct integers. An index is called a separator if the following two conditions hold:

• for all ,
• for all .

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

For instance, let . The separators are the indices and , corresponding to the values and .

The sequence is initially empty. You are given a sequence of elements to append to , one after another. After appending each , output the current number 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 you should append to , you are given a sequence .

Process the input as follows:

The empty sequence contains separators.

For each from to , inclusive:

1. Calculate the value .
2. Append to the sequence .
3. Calculate : the number of separators in the current sequence .
4. Output a line containing the value .

#### Input

The first line contains a single integer : the number of queries to process.

Then, lines follow. The -th of these lines contains the integer . The values are chosen in such a way that the values you'll compute will all be distinct.

#### Output

As described above, output lines with the values through .

#### 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 .