Magic: The Gathering 卡牌游戏有一个关于施放和反制法术的有趣机制。我们在此不作解释，因为它相当复杂，且对于解决本题并非必要。然而，如果你是一位 MtG 玩家，你可能会看出本题与法术反制机制之间的联系。

题目描述

对于每一棵有根树，都存在一种唯一的将顶点染成两种颜色（黑色和白色）的方法，满足以下约束： * 一个顶点为白色，当且仅当它拥有一个黑色儿子。

这种着色的唯一性可以通过归纳法轻松证明。我们将以这种方式着色的树称为“良构着色树”（well-colored）。

我们从一棵仅包含一个黑色顶点（根节点）的有根树开始，并执行 $n$ 次以下操作： * $add(v)$ —— 将一个新的黑色顶点作为顶点 $v$ 的儿子添加到树中。然后，反转树中某些（可能为零，可能为全部）顶点的颜色，使得结果树依然是良构着色树。

对于每次操作，我们希望知道在此过程中有多少个顶点的颜色被反转。

输入格式

树的根节点编号为 $0$，其他顶点按照添加到树中的顺序编号为 $1, 2, \dots, n$。

输入的第一行包含一个整数 $n$ ($1 \le n \le 200000$)，表示顶点添加的次数。 接下来 $n$ 行，第 $i$ 行包含一个整数 $v_i$，表示第 $i$ 次操作中添加的顶点的父亲编号。保证顶点 $v_i$ 在第 $i$ 次操作前已经存在，即 $v_i < i$。

输出格式

对于每次操作，输出一行，包含在此操作中颜色被反转的顶点数量。

子任务

样例

输入 1

5
0
1
2
1
3

输出 1

1
2
3
2
2

说明

每次操作后的情况如下所示（在之前操作中被反转的顶点已高亮显示）：