愚直にやると計算量 \(O(N^3)\) で全然間に合わない.

そこで転倒数の概念を使う. 入れ替えが1回行われるごとに転倒数が1減り, 最終的にはソート済の転倒数 \(0\) の状態になるので, 転倒数が \(cnt\) と等しい.

転倒数の計算は Fenwick Tree を使えば計算量 \(O(N \log N)\) で行えるので, 全体では計算量 \(O(N^2 \log N)\) となる. なお, Fenwick Tree を使うためには \(A_i\) は座標圧縮しておかなければならない.

しかし, これでもまだ間に合わない.

ここで \(i\) が増えると転倒数がどうなるか考える. 配列は最初の要素が取り除かれ, その要素が最後に追加される. よって最初の要素より小さい要素の数だけ転倒数は減り, 最後の要素より大きい要素の数だけ転倒数は増える. この数は \(A_i\) をソートした配列を別に用意しておけば二分探索で求めることができる. これにより計算量 \(O(N \log N)\) となり間に合う.