题目描述
二叉查找树是一种特殊的二叉树(每个节点最多只有两个儿子的树)。树的每个节点上存有一个唯一的值，并且满足：这个节点的左子树内所有点的值都比这个节点的值小，且右子树内所有点的值都比这个节点的值要大。
对于一棵二叉查找树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$ ）。
输入
输入的第一行一个整数 $n$，表示序列长度。
以下 $n$ 行是序列中的数字，这些数字是各不相同的，在 $[1,n]$ 区间。
输出
输出 $n$ 行，第 $i$ 行整数表示第 $i$ 个数插入树后，至这个节点的节点深度总和。
样例输入输出
输入#1
复制
8
3
5
1
6
8
7
2
4
输出#1
复制
0
1
2
4
7
11
13
15
提示
对于 $100\%$ 的数据，$N \leq 3 \times 10^5$。