题目描述

给定一个由 $1,2,\ldots,N$ 组成的排列 $p_1,p_2,\ldots,p_N$。你可以进行若干次（可以为 $0$ 次）如下操作：

操作：选择排列中相邻的两个数并交换它们。

请通过若干次操作，使得对于任意的 $1\leq i\leq N$，都满足 $p_i\neq i$。请你求出所需操作的最小次数。

输入格式

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

$N$ $p_1$ $p_2$ … $p_N$

输出格式

输出所需操作的最小次数。

样例 1

输入

5
1 4 3 5 2

输出

2

样例 2

输入

2
1 2

输出

1

样例 3

输入

2
2 1

输出

0

样例 4

输入

9
1 2 4 9 5 8 7 3 6

输出

3

说明/提示

限制条件

• $2\leq N\leq 10^5$
• $p_1,p_2,\ldots,p_N$ 是 $1,2,\ldots,N$ 的一个排列。

样例说明 1

将 $1$ 与 $4$ 交换，然后将 $1$ 与 $3$ 交换，排列变为 $4,3,1,5,2$，此时满足题目要求。这是所需的最少交换次数，因此答案为 $2$。

样例说明 2

只要交换 $1$ 与 $2$ 即可满足条件。

样例说明 3

初始排列已经满足条件。

由 ChatGPT 5 翻译