给定一个有根树,将树中顶点 $$$u$$$ 的值递归地定义为其子节点值的 MEX$$$^\dagger$$$ 。请注意,这只是子级,而不是其所有后代。特别是,叶子的价值是$$$0$$$。
Pak Chanek 有一个有根树,最初只包含索引为 $$$1$$$ 的单个顶点,即根。 Pak Chanek 将进行 $$$q$$$ 查询。在第 $$$i$$$ 查询中,Pak Chanek 被赋予一个整数 $$$x_i$$$。 Pak Chanek 需要添加一个索引为 $$$i+1$$$ 的新顶点作为顶点 $$$x_i$$$ 的子顶点。添加新顶点后,Pak Chanek 需要重新计算所有顶点的值并报告当前树中所有顶点的值的总和。
$$$^\dagger$$$ 数组的 MEX(排除最小值)是不属于该数组的最小非负整数。例如,$$$[0,1,1,2,6,7]$$$ 的 MEX 为 $$$3$$$,$$$[6,9]$$$ 的 MEX 为 $$$0$$$。
输入
第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — 操作数。
接下来的 $$$q$$$ 行包含一个整数 $$$x_i$$$ ($$$1 \leq x_i \leq i$$$) — 第 $$$i$$$ 查询的描述。
输出
对于每个查询,打印一行,其中包含一个整数,表示添加顶点后树中所有顶点的新值之和。
示例
输入 #1
7 1 1 3 2 5 2 1
输出 #1
1 1 3 2 4 4 7
输入 #2
8 1 1 1 1 5 6 7 8
输出 #2
1 1 1 1 3 2 4 3
注意
在第一个示例中,第 $$$6$$$ 查询之后的树将如下所示。
- 顶点 $$$7$$$ 是叶子,因此其值为 $$$0$$$。
- 顶点 $$$6$$$ 是叶子,因此其值为 $$$0$$$。
- 顶点 $$$5$$$ 只有一个值为 $$$0$$$ 的子节点,因此其值为 $$$1$$$。
- 顶点 $$$4$$$ 是叶子,因此其值为 $$$0$$$。
- 顶点 $$$3$$$ 只有一个值为 $$$0$$$ 的子节点,因此其值为 $$$1$$$。
- 顶点 $$$2$$$ 的子节点的值为 $$$0$$$ 和 $$$1$$$,因此其值为 $$$2$$$。
- 顶点 $$$1$$$ 的子节点的值为 $$$1$$$ 和 $$$2$$$,因此其值为 $$$0$$$。
所有顶点的值之和为$$$0+0+1+0+1+2+0=4$$$。