[ABC072D] Derangement

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

[problemUrl]: https://atcoder.jp/contests/abc072/tasks/arc082_b $ 1,2,..,N $ からなる順列 $ p_1,p_2,..,p_N $ が与えられます。 次の操作を何回か ($ 0 $回でもよい) 行うことが出来ます。 操作: 順列で**隣り合う**二つの数を選んでスワップする。 何回か操作を行って、任意の $ 1\ <\ =i\ <\ =N $ に対して $ p_i\ ≠\ i $ となるようにしたいです。 必要な操作の最小回数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ p_1 $ $ p_2 $ .. $ p_N $

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

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 初めから条件を満たしています。