← 返回题目列表

Codeforces · 347/B

B. 固定点

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

长度为 n 的排列是一个整数序列,使得从 0 到 (n - 1) 的每个整数在其中恰好出现一次。例如,序列 [0, 2, 1] 是长度为 3 的排列,而 [0, 2, 2] 和 [1, 2, 3] 则不是。

函数的不动点是由函数映射到其自身的点。排列可以被视为双射函数。我们将得到排列中不动点的定义。当且仅当 ai = i 时,整数 i 是排列 a0, a1, ..., an - 1 的不动点。例如,排列 [0, 2, 1] 有 1 个固定点,排列 [0, 1, 2] 有 3 个固定点。

给你排列 a。您最多可以交换排列中的两个元素一次。您的任务是最大化所得排列中的固定点数。请注意,您最多可以进行一次交换操作。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105)。第二行包含 n 个整数 a0, a1, ..., an - 1 — 给定的排列。

输出

打印一个整数 - 最多一次交换操作后排列中固定点数的最大可能数量。

示例

输入 #1

5
0 1 3 4 2

输出 #1

3