最小の操作回数は必ず \(2\) 以下です． \(0,1,2\) 回のケースをそれぞれ処理します．

\(0\) 回のケースは自明です．

\(1\) 回でできる条件を考えます． \(X_i=0\) を満たす最小の \(i\) を \(L\) と置きます． \(X_i=1\) を満たす最大の \(i\) を \(R\) と置きます． \(L>R\) のとき，\(X=(1,\cdots,1,0,\cdots,0)\) という形なので，全体をリバースすればよいです．

\(L<R\) の時を考えます． 一般性を失わず，\(X_L\) をグループAに入れたとします． \(L\) より右にある \(1\) をグループAに入れると，操作後に \(X\) がソートされないので，\(L\) より右の \(1\) はすべてグループBに入ります． 特に\(X_R\)はグループBに入り，同様の議論により，\(R\) より左の \(0\) はすべてグループAに入ります．

よって，\(X_L,\cdots,X_R\) のグループ分けは確定します． ここで，\(X\) に含まれる \(0\) の個数を \(C\) とします． \(C<i<R\) かつ \(X_i=0\) を満たす \(i\) の個数を \(D\) とします． これら \(D\) 個の場所はグループAに入りますが，操作後これらの場所は，\(i<L,\ i \leq C\) を満たす \(i\) と交換される形になるはずです． ここから，\(\min(L-1,C)\geq D\) という条件が導かれます．

実はこれは \(X\) が \(1\) 回でソートできる十分条件になっています． 実際に，\(\{1,\cdots,D\}\) と「\(L \leq i \leq R,\ X_i=0\) を満たす \(i\) 全部」をグループAに割り振り，それ以外を全部グループBに割り振ることで，\(X\) をソートできます．

\(X\) が \(1\) 回でソートできる条件がわかりました． 最後に，どんな \(X\) でも \(2\) 回でソートできることを示します．

先程に引き続いて \(0\) の個数を \(C\) とします． 一般性を失わず，\(C \geq N-C\) とします． \(X\) の先頭 \(N-C\) 項に含まれる \(0\) の個数を \(P\) 個とします． これら \(P\) 個の要素と，\(X\) の末尾 \(P\) 個の要素をグループAに割り振り，残り全部をグループBに割り振ることにします．

このグループ分けで一度操作をすると，\(X\) の後ろ \(N-C\) 項は，\(1,\cdots,1,0,\cdots,0\) という形になります． このとき，\(X\) を \(1\) 回の操作でソートできるための条件が満たされていることが確認できます．

よって，どんな \(X\) でも \(2\) 回以下の操作でソート可能であることが証明できました． 証明で示した手順をそのまま実装すれば，計算量 \(O(N)\) の解法になります．

回答例(C++)