分数: 500 点
问题陈述
给你一个序列 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第一场比赛将按如下方式进行。
- 青木指定一个正整数 K_i.
- 知道后 K_i 青木已指定,高桥选择一个整数 S_i 之间 1 和 N,包含在内,并将其写在黑板上。
-
重复以下操作 K_i 次。
- 替换整数 x 黑板上写着 黑板上写着 A_x.
If 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),所以青木获胜。
另一方面,在第二轮和第三轮中,高桥可以通过写来获胜 2 和 3,分别在初始黑板上,青木指定的任何值 K_i.
因此,如果两名玩家都以最佳状态获胜,则 Takashi 赢得两轮:第二轮和第三轮。因此,您应该打印 2.
示例输入 2
2 2 1
示例输出 2
2
第一轮,高桥写字即可获胜 2 在初始黑板上如果 Aoki指定的 K_1 是奇数,并且 1 如果是偶数。
同样,高桥也有办法赢得第二轮。因此,高桥可以赢得两轮比赛:答案是 2.