相信大家对二叉查找树都很熟悉了，现在给你N个整数的序列，每个整数都在区间[1,N]内，且不重复。现在要你按照给定序列的顺序，建立一个二叉查找树，把第一个整数作为根，然后依次插入后面的整数。
每个结点X的插入过程其实就是模拟下面的insert(X, root)过程:
insert (number X, node N) 
{
    increase the counter C by 1 //每次进来都会使C加1
    if X is less than the number in node N //如果X小于结点N的值
    {
        if N has no left child //N没有左孩子
    create a new node with the number X and set it to be the left child of node N //新建一个节点，把X作为N的左孩子
else
    insert(X, left child of node N) //递归插入到N左子树
    } 
    else (X is greater than the number in node N) //如果X大于结点N的值
    {
if N has no right child //N没有右孩子
    create a new node with the number X and set it to be the right child of node N //新建一个节点，把X作为N的右孩子
else
    insert(X, right child of node N) //递归插入到N右子树
    }
}

你的任务是:每次把序列的一个整数插入到二叉查找树后，输出到目前为止计数累加器C的值是多少?注意:第一次插入根时，计数器C的值是0。

第一行为一个整数N，表示序列中有多少个整数(1≤N ≤100000)。
接下来有N行，每行一个整数X，X在区间[1,N]内，且不重复，这N个整数组成了一个有序的序列。

N行，每行一个整数，第一行表示把序列的第一个数插入到二叉查找树后，当前计数器C的值是多少。

样例1说明:
第一次插入根1，不执行过程insert(number x, node N)，所以C是0，第二次插入2,C加1,所以插入2完毕后，输出C的值是1，第三次插入3，依次执行了insert(3,1)、insert(3,2)，所以C加2，变成3;第四次插入4，依次执行了insert(4,1)、insert(4,2)、insert(4,3)，所以C加3，变成6。


样例2：
输入：
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