[1] 必要条件

操作における不変量を考えます。（不変量についての参考資料：ABC 288 - D 解説）

任意の操作は、偶数回の隣接 swap によって表現することができます。このことから、転倒数は偶数変化することが分かります。つまり、操作の前と後で転倒数の偶奇は変化しません。

昇順に並び替えられた状態の転倒数は \(0\) なので、与えられた \(P\) の転倒数が奇数の場合 No であることがわかります。

[2] 構築方法

実は、[1] の必要条件を満たすならば常に \(2000\) 回以下の操作で \(P\) を昇順に並び替えられます。

以下の手続きを終了するまで繰り返せば良いです。

• \(P_m\neq m \) を満たす最小の \(m\) を見つける。そのような \( m\) が存在しない場合、\(P\) は昇順になっているので終了する。

• \(P_k=m\) なる \(k\) について、\(k < N\) ならば \(i=k, j = m-1\) として操作を行う。そうでない場合、一度 \(i=N-1,j=N-3\) として操作を行ってから、 \(i=k, j = m-1\) として操作を行う。

上の手続きは \(m=N-1\) のときは上手く行きませんが、\(m=N-1\) になることは転倒数が偶数という条件からありえません。また、\(1\) 回の手続きにより必ず \(m\) は \(1\) 以上増加する（または \(P\) が昇順になる）ので、上の手続きは高々 \(N-2\) 回の繰り返しにより終了します。

よって、 \(2000\) 回以下の操作で \(P\) を昇順に並び替えられます。