条件を満たしていない最小の \(i\) を \(x\) とおきます．

\(x \equiv 1 \mod 2\) のケースを考えます．

今，\(P_x>P_{x+1}\) です． \(P_x\) と \(P_{x+2}\) の大小関係に応じて，以下のように操作してみます．

• \(P_x>P_{x+2}\) のとき（もしくは \(x=2N-1\) のとき）：\(P_x,P_{x+1}\) を swap する．
• \(P_x<P_{x+2}\) のとき：\(P_{x+1},P_{x+2}\) を swap する．

このように操作すると，\(i=x,x+1\) で条件が満たされるようになります． \(P_{x-1}>P_x>P_{x+1}\) なので，\(i=x-1\) の条件も満たされたままです．

\(x \equiv 0 \mod 2\) の場合も同様の操作を行うことができます．

結局，\(1\) 度操作を行うごとに，「条件を満たしていない最小の \(i\)」の値は少なくとも \(2\) 増えるので，高々 \(N\) 回の操作で \(P\) 全体が条件を満たすようになります．

以上の手順を実装すれば，\(O(N)\) 時間でこの問題を解けます．

解答例(c++)