题目描述

$1,2,..,N$ からなる順列 $p_1,p_2,..,p_N$ が与えられます。 次の操作を何回か ($0$回でもよい) 行うことが出来ます。

操作: 順列で隣り合う二つの数を選んでスワップする。

何回か操作を行って、任意の $1\ <\ =i\ <\ =N$ に対して $p_i\ ≠\ i$ となるようにしたいです。 必要な操作の最小回数を求めてください。

输入格式

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

$N$ $p_1$ $p_2$ .. $p_N$

输出格式

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

题目大意

给你一段长为$N$的序列$p$,你每次可以进行操作交换两个相邻的元素
问最少要几次才能满足任意$i\in[1,N],p_i \neq i$

5
1 4 3 5 2

2

2
1 2

1

2
2 1

0

9
1 2 4 9 5 8 7 3 6

3

提示

制約

• $2\ <\ =N\ <\ =10^5$
• $p_1,p_2,..,p_N$ は $1,2,..,N$ の順列である。

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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