#AT1124. D - Derangement
D - Derangement
当前没有测试数据。
D - Derangement
Score : $400$ points
Problem Statement
You are given a permutation $p_1,p_2,...,p_N$ consisting of $1$,$2$,..,$N$. You can perform the following operation any number of times (possibly zero):
Operation: Swap two adjacent elements in the permutation.
You want to have $p_i ≠ i$ for all $1≤i≤N$. Find the minimum required number of operations to achieve this.
Constraints
- $2≤N≤10^5$
- $p_1,p_2,..,p_N$ is a permutation of $1,2,..,N$.
Input
The input is given from Standard Input in the following format:
..
Output
Print the minimum required number of operations
5
1 4 3 5 2
2
Swap $1$ and $4$, then swap $1$ and $3$. $p$ is now $4,3,1,5,2$ and satisfies the condition. This is the minimum possible number, so the answer is $2$.
2
1 2
1
Swapping $1$ and $2$ satisfies the condition.
2
2 1
0
The condition is already satisfied initially.
9
1 2 4 9 5 8 7 3 6
3