You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

你是爱野星的粉丝，自从爱野星【数据删除】了之后，你自己组建了一个偶像团体。

题目描述

偶像团体中，每个成员都有一个实力值，实力值是会变化的。当实力值集合为 $S$ 的团体演出的时候，其观赏性是最小未出现在 $S$ 当中的非负整数。

• 如实力值为 $\{0,1,1,2,2,3,5,5,6\}$ 的团体观赏性为 $4$。
• 如实力值为 $\{1\}$ 的团体观赏性为 $0$。

一开始，这个偶像团体只有你一个人。你的实力为 $0$，编号为 $1$。

由于种种原因，你只能一个一个地收集成员。每次新接入一个成员，你会给她安排编号为已有编号的后延（记为 $i$），并给她安排一个师傅 $f_{i-1}$。由于每个师傅经常和她的徒弟们一起演出，为了适应徒弟，师傅会调整自己的实力值为使她和徒弟们组成团体演出观赏性最高的一个实力值，可以证明，这样的值是唯一的。

• 如一个人没有徒弟，那么会把自己实力值设为 $0$。因为这时候团体的观赏性为 $1$。其余时候都是 $0$。
• 如果一个人徒弟实力值为 $\{0,1,1,3,4,6\}$，那么她会把自己的实力值调整为 $2$，这时整个团体观赏性为 $5$。

现在，你知道每个新接入成员的师傅。每次加入成员之后输出当前所有人的实力值之和。

输入格式

第一行一个正整数 $n$ 表示加入的次数。

接下来一行，$n$ 个正整数 $f_i$ 表示新接入成员的师傅编号。

输出格式

输出一行 $n$ 个正整数，表示每次接入后的答案。

测试样例

样例 $1$ 解释

接入第一个人之后，实力值为 $[1,0]$。

接入第二个人之后，实力值为 $[1,0,0]$。

接入第三个人之后，实力值为 $[2,1,0,0]$。

这是因为：

• $3,4$ 是叶子，实力值为 $0$。
• $2$ 的徒弟 $4$ 实力值为 $0$，为了最大观赏性把实力值设为 $1$。
• $1$ 的徒弟 $2,3$ 实力依次为 $0,1$。为了最大观赏性把实力值设为 $2$。

样例 $4$ 解释

该样例满足测试点 $3$ 的性质。

样例 $5$ 解释

该样例满足测试点 $5$ 的性质。

样例 $6$ 解释

该样例满足测试点 $10$ 的性质。

数据范围

对于所有数据，满足 $n\leq 10^6$，$f_i\leq i$。