← 返回题目列表

AtCoder · arc082_b

D. 精神错乱

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

分数: 400 点

问题陈述

给你一个排列 p_1,p_2,...,p_N 组成 1,2,..,N。 您可以执行以下操作任意次数(可能为零):

操作:交换两个 相邻 排列中的元素。

你想要 p_i ≠ i 对于所有人 1≤i≤N。 找出实现这一目标所需的最少操作数。

约束

  • 2≤N≤10^5
  • p_1,p_2,..,p_N 是一个排列 1,2,..,N.

输入

输入由标准输入按以下格式给出:

N
p_1 p_2 .. p_N

输出

打印所需的最少操作次数


示例输入 1

5
1 4 3 5 2

示例输出 1

2

交换 1 和 4,然后交换 1 和 3. p 现在 4,3,1,5,2 并满足条件。 这是可能的最小数,所以答案是 2.


示例输入 2

2
1 2

示例输出 2

1

交换 1 和 2 满足条件。


示例输入 3

2
2 1

示例输出 3

0

最初已满足条件。


示例输入 4

9
1 2 4 9 5 8 7 3 6

示例输出 4

3