部分点のコードを用いて実験すると、\(N\geq 7\) のときは常に昇順に並び替えられそうなことがわかります。

\(N\geq 6\) のときは部分点解法を用いることにして、以下、\(N\geq 7\) の場合を考えます。

---

[1] \(N\) が奇数の場合

はじめに一度全体に対し操作をすると、\(P\) は以下の構造となります。

o…ox…xmo…ox…x

ここで、m は \(P\) の中央値、o は m 未満の値、x は m より大きい値を意味します。m より左にあるx の個数を \(a\)、m より右にあるo の個数を \(b\) として場合分けをします。\(a\geq b\) を仮定します（\(a < b\) の場合も同様に解けます）。

(i) \(a = b \) のとき

\((\)x \(\times a\), m,o \(\times (b-2))\) に対して操作を行います。すると操作により選んだ列は \((\)x,o \(\times (b-2)\), m,x \(\times (a-1))\) に変化します。次に全体に操作すると、\(P\) は o…oxmoox…x になります。

その後 moo に操作し、\(P\) は o…oxomox…x となります。

moxxx に操作してから全体に操作して、o…oxmx…x を得ます。

最後に oooxm に操作し、全体に操作すると sort が完了します。

\(b=1\) のときは例外です。oooxm に操作をしてから全体に操作し o…omox…x を得ます。

次にmoxxx に操作をしてから全体に操作をすると sort が完了します。

(ii) \(a = b + 1\) のとき

\((\)x \(\times a\), m,o \(\times (b-1))\) に対して操作を行います。すると操作により選んだ列は \((\)x,o \(\times (b-1)\), m,x \(\times (a-1))\) に変化します。 次に全体に操作すると、\(P\) はo…oxmox…x になります。

moxxx に操作し、全体に操作して、 o…oxmx…x を得ます。

最後に oooxm に操作し、全体に操作すると sort が完了します。

(iii) \(a \geq b+2\) のとき

\((\)x \(\times (b + 2)\), m,o \(\times b)\) に対して操作を行います。すると操作により選んだ列は \((\)o \(\times b\), m,x \(\times (b + 2))\) に変化します。次に全体に操作すると、\(P\) は o…ox…xmx…x になります。

残りの課題は、o…ox…xmx…x を sort することです。

m の位置に着目しましょう。m の後ろに x が \(2\) つ以上ある場合は簡単です。

o…ox…xm を o が中央値になるように操作可能で、のちに全体に操作すれば sort が完了します。

そうでない場合は、 xxmとして操作を高々二回すれば上のケースに帰着されます。

これで \(N\) が奇数の場合は高々 \(7\) 回の操作で \(P\) を sort できました。

---

[2] \(N\) が偶数の場合

始めに \(P\) の先頭 \(N-1\) 項を [1] の手順で sort します。sort 後の \(P_N\) を \(B\) とします。 \(B\) の値で場合分けをします。

(i) \(B=N\) のとき

既に sort が完了しています。

(ii) \(B=N-1\) のとき

\((N-4,N-3,N-2,N,N-1)\) にたいして操作をすることで sort が完了します。

(iii) \(\frac{N}{2}<B < N-1\) のとき

\((N-1,N,B)\) に操作をしてから、\((1,\ldots,N-1,B)\) に操作をすればよいです。

(iv) \(B = \frac{N}{2}\) のとき

\((N-1,N,B)\) に操作をすると、o…ox…xm をsort できればよいです。これは [1] の(iii) の例と同じであり、最後の全体への操作が省略できることを踏まえると \(3\) 回の操作で可能です。

(v) \(B < \frac{N}{2}\) のとき

\((N-1,N,B)\) に操作をしてから全体に操作をします。o…omBx…x をsort できればよいです。これはmBxxx に操作してから全体に操作すればよいです。

結局 \(N\) が偶数の場合も \(11\) 回以下の操作で sort できることが示されました。