公式解説より計算量は悪いですが、別の視点からアプローチした解法を紹介します。

数列 \(A\) について \(A\) の転倒数を \(\mathrm{inv}(A)\) で表記することにします。

結論から述べると、答えが Yes であるための必要十分条件は以下の \(2\) つが満たされることです。

• 任意の \(i\) について、\(p_i\) と \(i\) の偶奇が一致している
  
• \(p\) の奇数項目のみを抜き出した数列を \(x\) , 偶数項目のみを抜き出した数列を \(y\) として、\((\mathrm{inv}(x) +\mathrm{inv}(y)) \times 3 = \mathrm{inv}(p)\)
  

必要性は、操作はすべて奇数項目どうし、あるいは偶数項目どうしの swap であり、また \(1\) 回の操作で \(\mathrm{inv}(x) + \mathrm{inv}(y)\) は \(1\) , \(\mathrm{inv}(p)\) は \(3\) 減少することから従います。

次に十分性を示します。
操作が可能となる条件を \(p_{i-1} > p_{i+1}\) に緩和することを考えます。このとき、 \(\mathrm{inv}(x) + \mathrm{inv}(y)\) 回操作を行うと、任意の \(i\) について \(p_i = i\) となります。\(1\) 回の操作で \(\mathrm{inv}(p)\) は高々 \(3\) しか減少しないことを考えると、すべての操作において \(\mathrm{inv}(p)\) は \(3\) 減少していることがわかり、これはすべての操作において実は \(p_{i-1} > p_i > p_{i+1}\) が満たされていたことを意味しています。

以上より必要十分性が示され、転倒数の計算は BIT などを用いることにより \(\mathrm{O}(N\log N)\) でできるので、この問題を \(\mathrm{O}(N\log N)\) で解くことができました。