Binary search tree

A binary search tree is a tree in which every node has at most two children nodes (a left and a right child). Each node has an integer written inside it. If the number $X$ is written inside a node, then the numbers in its left subtree are less than $X$ and the numbers in its right subtree are greater than X. You will be given a sequence of integers between 1 and $N$ (inclusive) such that each number appears in the sequence exactly once. You are to create a binary search tree from the sequence, putting the first number in the root node and inserting every other number in order.

When inserting a new number $Y$ in a tree, you first traverse the tree as if you were searching for $Y$. When you arrive at a node $Z$ such that you canâ€™t continue searching for $Y$, you put $Y$ as a left or right son of $Z$ depending on if $Z>Y$ or $Z<Y$, so that after the insertion the tree will still be a binary search tree. After the insertion you add the depth of $Y$ to a counter $C$ and print the value of $C$. The counter $C$ is set to $0$ in the beginning.

The first line contains the integer $N$ $(1 \leq N \leq 300\, 000)$, the length of the sequence.

The remaining $N$ lines contain the numbers in the sequence, integers in the interval $[1, N]$. The numbers will be distinct.

Output $N$ integers each on its own line, the values of the counter $C$ after each number is inserted into the tree.

Sample Input 1 | Sample Output 1 |
---|---|

4 1 2 3 4 |
0 1 3 6 |

Sample Input 2 | Sample Output 2 |
---|---|

5 3 2 4 1 5 |
0 1 2 4 6 |

Sample Input 3 | Sample Output 3 |
---|---|

8 3 5 1 6 8 7 2 4 |
0 1 2 4 7 11 13 15 |