Bookshelf 2

操作の性質により、値を交換する添え字の偶奇は同じです。

よって、奇数の添え字と偶数の添え字の列にそれぞれ分け、昇順に並び替えて復元することにより、 昇順に並び替えられるかどうかの判定が可能です。

また、昇順に並び替えられる場合の求める答えは、それぞれの列の転倒数の和となります。

これは、Segment Tree などにより $O(N \log N$) で求めることができ十分高速です。