题目描述

小理喜欢 OI。在 $9102$ 年的 PION 中，他在初赛遇到了这样一道题目： 阅读下列代码，然后回答问题。

补充：建树过程中会更新 $lc$ 和 $rc$，这实质上是一个二叉查找树的插入过程。 定义一个玄学节点叫做 $R$，每次操作读入 $val$ ，执行 Insert$(R,val)$。

问题：每次 Insert 操作结束之后，输出当前节点的深度和。 这里我们定义 $R$ 节点的深度为 $0$。

输入格式

输入共 $N+1$ 行。

第一行一个整数 $N$，表示操作次数。

接下来 $N$ 行，第 $i$ 行有一个值 $val_i$，表示第 $i$ 次操作的 $val_i$ 。

输出格式

输出共 $N$ 行，每行输出该次操作完后的答案。

样例输入输出

样例输入

8
3
5
1
6
8
7
2
4

样例输出

0
1
2
4
7
11
13
15

数据范围

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