分数: 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