D - Derangement

コンテスト時間: 2017-09-02(土) 12:00 ~ 2017-09-02(土) 13:40 (100分) AtCoderホームへ戻る

D - Derangement 解説

実行時間制限: 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$

出力

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

入力例 1Copy

Copy

5
1 4 3 5 2

出力例 1Copy

Copy

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

入力例 2Copy

Copy

2
1 2

出力例 2Copy

Copy

$1$ と $2$ を入れ替えれば条件を満たします。

入力例 3Copy

Copy

2
2 1

出力例 3Copy

Copy

初めから条件を満たしています。

入力例 4Copy

Copy

9
1 2 4 9 5 8 7 3 6

出力例 4Copy

Copy

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 1Copy

Copy

5
1 4 3 5 2

Sample Output 1Copy

Copy

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 2Copy

Copy

2
1 2

Sample Output 2Copy

Copy

Swapping $1$ and $2$ satisfies the condition.

Sample Input 3Copy

Copy

2
2 1

Sample Output 3Copy

Copy

The condition is already satisfied initially.

Sample Input 4Copy

Copy

9
1 2 4 9 5 8 7 3 6

Sample Output 4Copy

Copy