P6412 [COCI 2008/2009 #3] BST

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

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

#### 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](https://hsin.hr/coci/archive/2008_2009) [Contest #3](https://hsin.hr/coci/archive/2008_2009/contest3_tasks.pdf). Translated by ChatGPT 5