Description

You are given a permutation $a$ of $1 \sim n$. Insert the elements of the sequence into a BST one by one, and find the number of times the BST insertion function is executed.

Note: The first number is already the root of the BST.

If you do not understand the statement above, here is some pseudocode:

insert( number x, node n )
    c+1;
    if x is less than the number in node n
        if n has no left child
            create a new node with the number x and set it to be the left child of node n
     else
         insert(x, left child of node n)
     else (x is greater than the number in node n)
         if n has no right child
             create a new node with the number x and set it to be the right child of node n
         else
             insert(x, right child of node n) 

What you need to output is the value of $c$ after each call to the insert function.

Again: The first number is already the root of the BST.

Input Format

The first line contains an integer $n$, the length of the permutation $a$.

The next $n$ lines each contain an integer. The $i$-th of these lines is $a_i$.

Output Format

Output a total of $n$ lines, each containing an integer, representing the value of $c$ after each insertion (i.e., after each call of the insert function above).

4
1
2
3
4 

0
1
3
6

5
3
2
4
1
5 

0
1
2
4
6 

8
3
5
1
6
8
7
2
4 

0
1
2
4
7
11
13
15 

Hint

Constraints

• For $50\%$ of the testdata, $n \le 10^3$ is guaranteed.
• For $100\%$ of the testdata, $1 \le n \le 3 \times 10^5$, $1 \le a_i \le n$, and all $a_i$ are distinct.

Notes

This problem is translated from T5 BST of Croatian Open Competition in Informatics 2008/2009 Contest #3.

Translated by ChatGPT 5