一个排序二叉树的每个结点最多有两个儿子（左儿子和右儿子），每个结点上有一个整数，如果数字X在结点a上，则a的左子树上的所有值都小于X，而右子树上的值都不小于X。给定一个不重复的序列，（序列的元素共N个，值分别是1至N之间的数，且没有重复）你要用这个序列构成一个排序二叉树。首先将第一个元素放在树的根上，然后顺次插入其它元素。也就是运行程序insert(X, root)
程序如下：
insert( number X, node N )
increase the counter C by 1（也就是 counter c加1）
if X is less than the number in node N //（less than 是小于的意思）
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) //（greater than 是大于等的意思）
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)
写一个程序计算当插入所有元素后 counter C 的值，counter C 的初值为0.
输入：
第一行一个整数N(1 ≤ N ≤ 300 000), 表示序列的长度。
接下来N行，每行一个小于N的自然数。
输出：
N行，每行一个整数，表示插入的第i个数后counter C 的值。
注意：
50%数据 N 最多1000.
样例：
输入:
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