ギャグなのに時間かかった…

解法

まず元の配列の転倒数のパリティを愚直に求めよう(BITを使って $O(n \log n)$ でもとける)

転倒数のパリティはswapの偶奇に依存する(sawpの順番や、回数は直接関係ない)

よって長さが $d$ の配列の反転は $\dfrac{d (d - 1)} {2}$ 回swapすることで必ず達成できるので、 $\dfrac{d(d-1)}{2}$ の偶奇を見てしまえばおしまいである

提出コード

これに時間かかったのはダメだったね