/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 400 点
問題文
1,2,..,N からなる順列 p_1,p_2,..,p_N が与えられます。 次の操作を何回か (0回でもよい) 行うことが出来ます。
操作: 順列で隣り合う二つの数を選んでスワップする。
何回か操作を行って、任意の 1≤i≤N に対して p_i ≠ i となるようにしたいです。 必要な操作の最小回数を求めてください。
制約
- 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
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:
N p_1 p_2 .. p_N
Output
Print the minimum required number of operations
Sample Input 1
5 1 4 3 5 2
Sample Output 1
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.
Sample Input 2
2 1 2
Sample Output 2
1
Swapping 1 and 2 satisfies the condition.
Sample Input 3
2 2 1
Sample Output 3
0
The condition is already satisfied initially.
Sample Input 4
9 1 2 4 9 5 8 7 3 6
Sample Output 4
3