← 返回题目列表

Codeforces · 930/A

A. 奇特的苹果树

中文机器翻译题面 查看原题

阿卡迪的花园里长着一棵奇特的苹果树,每年结果一次。它的特殊性可以用以下方式解释:有n个花序,编号从1到n。 1 号花序位于树基部附近,任何其他编号为 i (i > 1) 的花序位于树枝顶部,底部为第 pi 个花序且 pi < i。

一旦树开始结果,每个花序中就会出现一个苹果。苹果出现的同时,它们就开始沿着树枝滚落到树的根部。每秒,除了第一个花序中的苹果外,所有苹果都会同时从靠近树根的一根树枝上滚下来,例如,第a个花序中的苹果到达第个花序。阿卡迪在同一时刻收集最终长出第一个花序的苹果。这棵树的第二个特点是,一旦两个苹果处于同一花序中,它们就会消失。每对苹果都会发生这种情况,例如如果同一时间同一花序有5个苹果,则只有一个不会被消灭,如果有8个苹果,则所有苹果都会被消灭。因此,在每个时刻,每个花序中最多只能有一个苹果。

帮助阿卡迪计算一次收获期间他能够从第一个花序收集的苹果数量。

输入

输入的第一行包含单个整数 n (2 ≤ n ≤ 100 000) — 花序数。

输入的第二行包含 n - 1 个整数 p2, p3, ..., pn (1 ≤ pi < i) 的序列,其中 pi 是第 i 个花序中的苹果向下滚动的花序数。

输出

单行输出应包含一个整数:Arcady 在一次收获期间能够从第一个花序收集的苹果数量。

示例

输入 #1

3
1 1

输出 #1

1

输入 #2

5
1 2 2 2

输出 #2

3

输入 #3

18
1 1 1 4 4 3 2 2 2 10 8 9 9 9 10 10 4

输出 #3

4

注意

在第一个示例中,Arcady 将只能收集一个最初位于第一个花序的苹果。下一秒,第二个和第三个花序的苹果将滚落并消失,阿卡迪将无法收集它们。

在第二个示例中,Arcady 将能够收集 3 个苹果。第一个是最初位于第一个花序的一个。在第二个苹果中,来自第二个花序的苹果将滚落到第一个花序(Arcady 将收集它),来自第三个、第四个、第五个花序的苹果将滚落到第二个花序。其中两个会消灭,一个没有消灭的会在下一秒从第二个花序滚落到第一个花序,Arcady 将收集它。