Binary Search Tree

A binary search tree is a tree where each node has at most two children. Each node stores one distinct integer. If a node stores the value X, then every value in its left subtree is smaller than X, and every value in its right subtree is greater than X.

You are given a permutation of the integers from 1 to N. Build a binary search tree by making the first number the root, then inserting all remaining numbers in the given order. In other words, for every number X except the first one, run insert(X, root).

The insertion function works as follows.

insert(number X, node N)
    increase counter C by 1
    if X is smaller than the value stored in node N
        if N has no left child
            create a new node storing X and make it the left child of N
        else
            insert(X, the left child of N)
    else
        if N has no right child
            create a new node storing X and make it the right child of N
        else
            insert(X, the right child of N)

The counter C is initially 0. After each number has been placed in the tree, print the current value of C. The first number, which becomes the root, is placed without calling insert.

The first line contains the size of the sequence, N. (1 <= N <= 300000)

Each of the next N lines contains one number of the sequence in order. The numbers are distinct integers between 1 and N, inclusive.

Print N lines. The i-th line must contain the value of counter C immediately after the first i numbers of the sequence have been placed in the tree.