题目描述

给定长度为 $N$ 的数列 $A=(A_1,A_2,\ldots,A_N)$，其中每个 $A_i$（$1\leq i \leq N$）满足 $1\leq A_i \leq N$。

高橋君和青木君将进行 $N$ 轮游戏。第 $i=1,2,\ldots,N$ 轮游戏的进行方式如下：

1. 青木君指定一个正整数 $K_i$。
2. 高橋君在听到青木君指定的 $K_i$ 后，选择一个 $1$ 到 $N$ 之间的整数 $S_i$，并写在黑板上。
3. 然后，重复以下操作 $K_i$ 次：
   • 如果黑板上写着数字 $x$，则擦掉它，并写上 $A_x$。

如果经过 $K_i$ 次操作后，黑板上写的是数字 $i$，则第 $i$ 轮游戏高橋君获胜；否则青木君获胜。 在这里，对于每个 $i=1,2,\ldots,N$，$K_i$ 和 $S_i$ 都可以独立选择。

当两人都采取最佳策略以赢得比赛时，请计算高橋君赢得的 $N$ 轮游戏中的胜场数。

输入格式

输入按照以下格式从标准输入提供：

N
A_1 A_2 … A_N

输出格式

当两人都采取最佳策略时，输出高橋君赢得的 $N$ 轮游戏中的胜场数。

3
2 2 3

2

2
2 1

2

提示

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq N$
• 所有输入值都是整数

示例解释 1

在第一轮游戏中，如果青木君指定 $K_1=2$，高橋君无法选择 $S_1$ 为 $1, 2, 3$ 中的任何一个来获胜。例如，如果高橋君最初在黑板上写上 $S_1=1$，那么两次操作将依次改变黑板上的数字为 $1 \to 2(=A_1)$，$2 \to 2(=A_2)$，最终黑板上的数字是 $2(\neq 1)$，因此青木君获胜。然而，在第二和第三轮游戏中，无论青木君指定的 $K_i$ 的值是什么，高橋君都可以分别通过最初在黑板上写上 $2, 3$ 来获胜。因此，如果两人都采取最佳策略来赢得比赛，高橋君将赢得第二和第三轮，总共赢得两轮，因此输出 $2$。

示例解释 2

在第一轮游戏中，高橋君可以通过在黑板上写上 $2$（如果青木君指定的 $K_1$ 是奇数）或 $1$（如果是偶数）来获胜。类似地，高橋君也有办法赢得第二轮游戏。因此，无论哪一轮，高橋君都能获胜，答案是 $2$。