Problem C
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.

Input

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

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

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