AtCoder Regular Contest 082

D - Derangement


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 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_N1,2,..,N の順列である。

入力

入力は以下の形式で標準入力から与えられる。

N
p_1 p_2 .. p_N

出力

必要な操作の最小回数を出力せよ。


入力例 1

5
1 4 3 5 2

出力例 1

2

14 を入れ替え、その後 13 を入れ替えることで p4,3,1,5,2 となり、これは条件を満たします。 これが最小回数なので、答えは 2 となります。


入力例 2

2
1 2

出力例 2

1

12 を入れ替えれば条件を満たします。


入力例 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

Submit提出する