操作 \(k\) に対し、 \(P\) の先頭 \(k\) 項に含まれる整数は「操作対象である」といいます。また、\(P_i=x\) に対し、 \(P_j > P_i, \ j < i\) を満たす \(j\) の数を「 \(x\) の転倒数への寄与」といいます。

操作 \(k\) が行われる際、操作対象である整数 \(x\) に対し、 \(x\) より左側にある \(x\) より大きい整数の数は（存在する場合）操作によって必ず \(1\) だけ減ります。また、 \(A\) が広義単調増加であることから一度 \(x\) が操作対象になった後は常に操作対象です。よって \(x\) が初めて操作対象になるのが \(l_x\) 回目の操作で、 初期状態において \(x\) より左側にある \(x\) より大きい整数の数が \(inv_x\) であるとき、 \(l_x\) 回目の操作から \(\min(M,l_x+inv_x)\) 回目の操作では \(x\) の転倒数への寄与は \(1\) ずつ減り、それ以降 \(x\) の転倒数への寄与は変化しません。

以上より各 \(x\) に対する \(l_x,inv_x\) が求まれば、各操作による転倒数の変化が imos 法で求めることができます。 \(l_x,inv_x\) はそれぞれ二分探索と fenwick tree を用いることで \(O(N\log M), O(N\log N)\) 時間で求めることができます。