背景

在某些游戏上只能显示为“火**印奔行者”（尤其是炉石传说！）

题目描述

有一棵无根树，初始时只有节点 $1$。

有 $n - 1$ 次操作，第 $i$ 次操作创建节点 $i + 1$，$i + 1$ 号节点的父亲为读入的 $x_{i + 1}$。

执行完每一次操作后，输出：

任意删去树中的两个节点，并删去所有与这两个节点直接相连的边，剩余部分所形成连通块个数的最大值。

输入格式

第一行一个整数 $n\ (2 \leq n \leq 3 \times 10^6)$。

接下来一行 $n - 1$ 个整数 $x_2,x_3,\cdots,x_n\ (1 \le x_i < i)$。

输出格式

一行 $n - 1$ 个整数表示答案。

8
1 1 1 4 5 1 4

0 1 2 3 4 5 5

提示

样例 1 解释

在第 $7$ 次操作后形成的树如上，此时选择删去 $1$、$4$ 节点，以及所有与它们直接相连的边，剩余的连通块数量为 $5$。不存在其他选法能使得剩余的连通块数量更多。

请使用较快的读入与输出方式。