答えは \(\frac{1}{2} \sum |P_i-i|\) です。

以下、\(f(P) = \sum |P_i-i|\) とします。

\(P\) が昇順であることと、\(f(P) = 0\) は同値です。

コスト和の下界として \(\frac{1}{2} \sum |P_i-i|\) がとれることを示します。
\(i,j\) を選ぶ操作による \(f(P)\) の変化量は \((|P_j-i| + |P_i-j|) - (|P_i-i|+|P_j-j|)\) です。操作の条件より \(P_i,P_j\) はどちらも \(i\) 以下または \(j\) 以上であることから、この変化量は \(0\) または \(-2(j-i)\) または \(2(j-i)\) です。つまり、コスト \(1\) に対して減らせる量は最大で \(2\) であるため、\(\frac{1}{2} \sum |P_i-i|\) は昇順にするために必要なコスト和の下界です。

この下界が達成可能であることを示します。
\(P\) が昇順で無い場合に、\(f(P)\) の値を \(-2(j-i)\) 変化させる \(i,j\) を選ぶことが常に可能です。
\(P_k \neq k\) となる \(k\) を小さい順に \(v_1,v_2,\cdots,v_t\) とします。\(P_{v_1}>v_1\) かつ \(P_{v_t} < v_t\) が成り立つため、\(P_{v_i}>v_i\) かつ \(P_{v_{i+1}}<v_{i+1}\) を満たす \(v_i,v_{i+1}\) が必ず存在します。そのような \(v_i,v_{i+1}\) を選ぶ操作を行えば良いです。

以上のことから求める値は \(\frac{1}{2} \sum |P_i-i|\) であり、これは \(O(N)\) で求めることが可能です。