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 then , 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:

- Calculate the value .
- Append to the sequence .
- Calculate : the number of separators in the current sequence .
- 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 .

#### Scoring

Subtask ( points): .

Subtask ( points): .

Subtask ( points): .

Subtask ( 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 .

## Comments