转移游戏

题目描述

给定 $N$ 个数的序列 $A=(A_1,A_2,\ldots,A_N)$。这里，每个 $A_i$ $(1\le i\le N)$ 都满足 $1 \le A_i \le N$。

高桥和青木将进行 $N$ 轮游戏。对于每个 $i=1,2,\ldots,N$，第 $i$ 轮游戏按以下方式进行。

1. 青木指定一个正整数 $K_i$。
2. 在得知青木指定的 $K_i$ 之后，高桥选择一个介于 $1$ 和 $N$ 之间（含两端）的整数 $S_i$，并将其写在黑板上。
3. 重复以下操作 $K_i$ 次：将黑板上写着的整数 $x$ 替换为 $A_x$。

如果经过 $K_i$ 次迭代后黑板上写的是 $i$，则高桥赢得第 $i$ 轮；否则青木获胜。

这里，$K_i$ 和 $S_i$ 可以对每个 $i=1,2,\ldots,N$ 独立选择。

在双方都为了获胜而最优行动的情况下，求高桥获胜的轮数。

输入格式

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

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

输出格式

输出在双方都为了获胜而最优行动的情况下，高桥获胜的轮数。

样例

3
2 2 3

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 1

2

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

类似地，第二轮也有办法让高桥获胜。因此高桥可以赢得两轮：答案是 $2$。

数据范围

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