CF1740H.MEX Tree Manipulation

Given a rooted tree, define the value of vertex $u$ in the tree recursively as the MEX$^\dagger$ of the values of its children. Note that it is only the children, not all of its descendants. In particular, the value of a leaf is $0$.

Pak Chanek has a rooted tree that initially only contains a single vertex with index $1$, which is the root. Pak Chanek is going to do $q$ queries. In the $i$-th query, Pak Chanek is given an integer $x_i$. Pak Chanek needs to add a new vertex with index $i+1$ as the child of vertex $x_i$. After adding the new vertex, Pak Chanek needs to recalculate the values of all vertices and report the sum of the values of all vertices in the current tree.

$^\dagger$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For example, the MEX of $[0,1,1,2,6,7]$ is $3$ and the MEX of $[6,9]$ is $0$.

给定一棵有根树，定义树中顶点 $u$ 的值为：其所有子节点（注意：仅指直接子节点，而非所有后代节点）的值所构成数组的 MEX$^\dagger$。特别地，叶子节点的值为 $0$。

Pak Chanek 拥有一棵初始仅含一个顶点（编号为 $1$）的有根树，该顶点即为根节点。Pak Chanek 将执行 $q$ 个查询。在第 $i$ 个查询中，Pak Chanek 会得到一个整数 $x_i$，他需要将一个新顶点（编号为 $i+1$）作为顶点 $x_i$ 的子节点加入树中。添加新顶点后，Pak Chanek 需要重新计算树中所有顶点的值，并报告当前树中所有顶点的值之和。

$^\dagger$ 数组的 MEX（最小未出现值）是指不属于该数组的最小非负整数。例如，$[0,1,1,2,6,7]$ 的 MEX 是 $3$，而 $[6,9]$ 的 MEX 是 $0$。

The first line contains a single integer $q$ ($1 \le q \le 3 \cdot 10^5$) — the number of operations.

Each of the next $q$ lines contains a single integer $x_i$ ($1 \leq x_i \leq i$) — the description of the $i$-th query.

第一行包含一个整数 $q$（$1 \le q \le 3 \cdot 10^5$）—— 操作的次数。

接下来的 $q$ 行中，每行包含一个整数 $x_i$（$1 \leq x_i \leq i$）—— 第 $i$ 个查询的描述。

For each query, print a line containing an integer representing the sum of the new values of all vertices in the tree after adding the vertex.

对于每个查询，输出一行，包含一个整数，表示在添加该顶点后树中所有顶点的新值之和。

In the first example, the tree after the $6$-th query will look like this.

• Vertex $7$ is a leaf, so its value is $0$.
• Vertex $6$ is a leaf, so its value is $0$.
• Vertex $5$ only has a child with value $0$, so its value is $1$.
• Vertex $4$ is a leaf, so its value is $0$.
• Vertex $3$ only has a child with value $0$, so its value is $1$.
• Vertex $2$ has children with values $0$ and $1$, so its value is $2$.
• Vertex $1$ has children with values $1$ and $2$, so its value is $0$.

The sum of the values of all vertices is $0+0+1+0+1+2+0=4$.

在第一个例子中，第 $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$。