\(N \leq 8\) は全探索。以降は \(N \geq 9\) について考える。

\(N\) が奇数

1. 全体に対して操作する（o…ox…xmo…ox…x 型になる）
2. 満点解法でいう \(a,b\) について、
   • \(a=b=0\)：ソート済みなので終了
   • \(a=0, b \ne 0\)：リバースして \(a \ne 0\) に帰着
   • \(a \ne 0\)：\(a=0\) にすることを目指す
     • \(1 \le a \le \lfloor \frac{N}{2} \rfloor - 2\)：x…xm とその周りの o を \(a+2\) 個選ぶ（x が全て m より右に移る）
     • \(a = \lfloor \frac{N}{2} \rfloor\)：xxxxm を選ぶ（x が \(2\) 個 m の右に移る）
     • \(a = \lfloor \frac{N}{2} \rfloor - 1\)：xxm を選ぶ（x が \(1\) 個 m の右に移る）
3. 1.に戻る

\(2\) ステップで \(a\) を \(0\) に出来るので、少なくとも \(5\) ステップ目で終わる。（\(9\) 手）
実際には \(a,b\) ともに \(2\) ステップかかるケースは存在しないため、最大でも \(7\) 手で終わる。

\(N\) が偶数

1. まず先頭 \(N-1\) 個をソート
2. 末尾で場合分け
   • \(N\)：ソート済み
   • \(N-1\)：末尾 \(5\) 個を選ぶとソートできる
   • \(N-2\) 以下：末尾 \(3\) 個を選ぶと \(N\) が末尾に来るので、先頭 \(N-1\) 個をもう一度ソート

少なくとも \(7+1+7=15\) 手で収まる。
実際には \(2\) 回目のソートではほぼソート済みなので、\(13\) 手に収まる。（例：10 9 8 7 6 4 3 2 1 5）

おまけ：10手で収める

偶数の 2. を \(3\) 手でできれば良い。

• \(\frac{N}{2}+1\)：末尾 \(3\) 個を選び、先頭 \(N-1\) 個を選ぶ
• \(\frac{N}{2}+1\) より大：末尾 \(N-1\) 個を選べばソートできる
• \(\frac{N}{2}+1\) 未満：末尾 \(N-1\) 個を選び、\([\frac{N}{2}-4,\frac{N}{2}]\) を選び、先頭 \(N-1\) 個を選ぶ