题目描述

给定一个由 $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$，第 $i$ 轮游戏的进行方式如下：

1. 青木指定一个正整数 $K_i$。

2. 在知道青木指定的 $K_i$ 后，高桥在 $1$ 到 $N$ 之间选择一个整数 $S_i$，并将其写在黑板上。

3. 重复以下步骤 $K_i$ 次：

   • 用 $A_x$ 替换黑板上写的整数 $x$。

如果 $i$ 写在黑板上经过 $K_i$ 次迭代后，高桥赢得第 $i$ 轮游戏；否则，青木赢。
这里，$K_i$ 和 $S_i$ 可以独立选择对于每个 $i=1,2,\\ldots,N$。

找出如果两位玩家都采取最佳策略来赢得游戏，高桥赢得的轮数。

约束条件

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

输入

输入以以下格式从标准输入给出：

$N$ $A_1$ $A_2$ $\\ldots$ $A_N$

输出

找出如果两位玩家都采取最佳策略来赢得游戏，高桥赢得的轮数。

示例输入 1

3
2 2 3

示例输出 1

2

在第一轮中，如果青木指定 $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
2 1

示例输出 2

2

在第一轮中，如果青木指定的 $K_1$ 是奇数，高桥可以通过在初始的黑板上写下 $2$ 来获胜；如果是偶数，则写下 $1$。

同样，在第二轮中，高桥也有办法获胜。因此，高桥可以赢得两轮：答案是 $2$。