概要

いくつかの方針が存在しそうです．

問題原案：Syntax_Error_

解説

$2$ 通りの解法を紹介します：

• ソートの過程をシミュレーションする．
• $i, P_i$ 間に辺を張った $N$ 頂点のグラフにおける連結成分の個数を考える．

シミュレーションをする解法

操作によって，好きな数を好きな位置に移動することができます．
既にソートされている部分を変更せずに，残りの部分を順に一致させていくことができます．

たとえば先頭から順に一致させていくことで最適な操作手順の一例が得られます．

「整数 $x$ は列 $P$ の何番目か？」という情報が分かればいいので，最初に $P_i = x$ となるような $i$ を $1 \leq x \leq N$ なるすべての整数について求めておいうたうえで，操作のシミュレーション時に $P$ と同時に更新していくとよいでしょう．(詳しくは実装例も参照してください．)

連結成分の個数を利用する解法

頂点 $1, 2, \ldots, N$ をもつ $N$ 頂点のグラフ $G$ を考え，頂点 $i \scriptsize \; (1 \leq i \leq N)$ と 頂点 $P_i$ とを結ぶ辺を張ります．

このとき，$($連結成分の大きさ$) - 1$ を $G$ のすべての連結成分について足し合わせた値，すなわち $N - ( G$ の連結成分の個数$)$ が答えに一致します．

これを証明します：

• 各辺を $i \to P_i$ の有向辺とする．
• すべての頂点は，入辺と出辺を $1$ 本ずつ持つから，$G$ はサイクルのみからなるグラフになる．
• また，頂点 $i$ と 頂点 $P_i$ とは同一の連結成分(サイクル)に属するから，連結成分ごとにソートすればよい．(これが最適)
  • 他の連結成分に属する頂点と交換する必要はないことを考えるとわかる．
• $K$ 頂点のサイクルをソートするには $K - 1$ 回の操作が最適で，この総和が答え．
  • $K = 1$ (自己ループ) のとき ：
    • $i = P_i$ となっている場合．ソートされているので $0 \,(= K - 1)$ 回．
  • $K > 1$ のとき：
    • $i = P_i$ なる $i$ は存在しない．
    • サイクルに属する頂点のうち一つを目的の位置に移動させると，大きさ $1, K-1$ の $2$ つにサイクルに分離する．
    • $K-1$ 回の分離で，大きさ $1$ のサイクル $K$ 個になる．

解説：uni_kakurenbo

実装例