Problem Description

Given a permutation \( a \) of \( 1 \sim n \), we sequentially insert the elements into a Binary Search Tree (BST). Your task is to determine the number of executions of the insertion function in the BST.

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

If you find the above description hard to understand, here is a 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)

You need to find the value of \( c \) after each execution of the insert function.

Again, note: The first number is already set as the root of the BST.

Input Format

The first line contains an integer \( n \), representing the length of the permutation \( a \).

The next \( n \) lines each contain an integer, where the \( i \)-th line is \( a_i \).

Output Format

Output \( n \) lines, each containing an integer representing the value of \( c \) after each execution of the insert function.

Sample Input and Output

Sample Input #1

4
1
2
3
4

Sample Output #1

0
1
3
6

Sample Input #2

5
3
2
4
1
5

Sample Output #2

0
1
2
4
6

Sample Input #3

8
3
5
1
6
8
7
2
4

Sample Output #3

0
1
2
4
7
11
13
15

Notes

Data Range and Constraints

• For 50% of the test cases, \( n \leq 10^3 \).
• For 100% of the test cases, \( 1 \leq n \leq 3 \times 10^5 \), \( 1 \leq a_i \leq n \), and all \( a_i \) are distinct.

Notes

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

见题面 Input 部分

见题面 Output 部分