给你一棵拥有 $n$ 个节点的有根树，节点编号为 $1$ 到 $n$，以节点 $1$ 为根。对于每个节点 $i$（$2 \le i \le n$），其父节点为 $p_i$。对于每个节点 $i$，如果它是叶子节点（即没有子节点的节点），则在其上写有整数 $i$。否则，不写任何内容。

如果 $u = v$，或者 $u$ 不是根节点且 $u$ 的父节点是 $v$ 的后代，则称节点 $u$ 是节点 $v$ 的后代。

现在，你和你的朋友在这棵树上玩一个游戏，双方轮流操作：你先手，然后是你的朋友，以此类推。在每个回合中，当前玩家必须选择一个节点 $v$，然后删除 $v$ 的整个子树（即 $v$ 的所有后代，包括 $v$ 本身）。只有在删除后，树中仍至少保留一个写有整数的节点时，该操作才是允许的。

当无法进行更多操作时，游戏结束。此时，树中恰好剩下一个写有整数的节点；游戏的分数就是该节点上的整数。

你的目标是使分数最小化，而你的朋友的目标是使分数最大化。假设你和你的朋友都采取最优策略，求游戏的分数。

输入格式

输入的第一行包含一个整数 $n$（$2 \le n \le 500\,000$）。

第二行包含 $n - 1$ 个整数 $p_2, p_3, \dots, p_n$（对于所有 $2 \le i \le n$，满足 $1 \le p_i < i$）。

输出格式

输出在双方均采取最优策略下的游戏分数。

样例

输入样例 1

7
1 2 2 1 5 5

输出样例 1

4

说明 1

给定的树如图 B.1 (a) 所示。

图 B.1：样例输入 #1 示意图。

双方唯一的最优操作如下：

• 你选择节点 5。然后节点 5、6 和 7 被删除（图 B.1 (b)）。
• 你的朋友选择节点 3。然后只有节点 3 被删除（图 B.1 (c)）。
• 你无法进行任何操作，游戏结束。

在这些操作之后，只剩下一个写有整数的节点，即节点 4。该游戏的分数为 4。

输入样例 2

9
1 1 3 2 5 4 5 5

输出样例 2

7

说明 2

给定的树如图 B.2 所示。

图 B.2：样例输入 #2 示意图。

你的其中一个最优操作是选择节点 2。在此之后游戏结束，分数为 7。