Description

二叉查找树是一种特殊的二叉树(每个节点最多只有两个儿子的树)。树的每个节点上存有一个唯一的值，并且满足：这个节点的左子树内所有点的值都比这个节点的值小，且右子树内所有点的值都比这个节点的值要大。

对于一棵二叉查找树 $T$，我们可以将一个值为 $val$ 的新点插入 $T$ 中，且保持树的性质。算法如下:

//lc[x]表示节点x的左儿子  

//rc[x]表示节点x的右儿子  

//num[x]表示节点x的权值  

void insert(int x, int val)

{

	if (val < num[x]) 

	{  

		if (!lc[x]) 

		{  

			lc[x] = ++T;  

			return ;  

		}  

		else   

			insert(lc[x], val);

	}

	else if (val > num[x])

	{

		if (!rc[x])

		{

			rc[x] = ++T;

			return ;

		}

		else

			insert(rc[x], val);

	}

}

需要将 $val$ 插入二叉查找树 $T$ 时，执行 insert(root, val)。

现在有 $N$ 个数需要插入一棵空树中。给定插入序列，请在每个元素被插入之后，输出所有节点的深度总和（根的深度为 $0$）。

Input Format

输入的第一行一个整数 $n$，表示序列长度。

以下 $n$ 行是序列中的数字，这些数字是各不相同的，在 $[1,n]$ 区间。

Output Format

输出 $n$ 行，第 $i$ 行整数表示第 $i$ 个数插入树后，至这个节点的节点深度总和。

Sample

输入样例：

8
3 
5 
1 
6 
8 
7 
2 
4

输出样例：

0 
1 
2 
4 
7 
11 
13 
15

Hint

对于 $50\%$ 的数据，$N\le 1000$；

对于 $100\%$ 的数据，$N\le 3\times 10^5$。