问题描述

在一个充满奇幻数字0101魔法的森林里，有一位勇敢的探索者小壹。小壹遇到了一个神奇的挑战。有一个包含 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没有左孩子
            //新建一个节点, 把X作为N左孩子
           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)//递归插入到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， 你可以理解为插入根是不执行insert()操作的， 其后每插入一个结点， C都累加， 也就是每次进入过程insert( number X, node N )， 都会执行increase the counter C by 1， 使得C不断增大。

格式

输入

第一行一个整数： N, 表示序列有多少个整数。 1 <= N <=300000接下来有 N 行， 每行一个整数 X, X 在区间[1,N]内， 且不重复， 这 N 个整数就组成了一个有序的序列。

输出

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

样例

4 1 2 3 4

0 1 3 6

提示

样例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。

【数据范围】

50%的数据： N <= 1000