\(P\) の inverse permutation \(Q\) を考えてみます． つまり，\(Q_{P_i}=i\) です．

操作を \(Q\) を主役にして言い換えてみると，以下のようになります．

• \(1 \leq i < j \leq N,\ Q_i-Q_j \geq K\) を満たす \(i,j\) を選ぶ． ただし，\((Q_i,Q_j)\) のペアは今までに選ばれたことがないものとする． \(Q_i,Q_j\) を swap する．

\(Q\) の疑似転倒数(ここだけの用語です)を以下のように定義します．

• \(i <j,\ Q_i-Q_j \geq K\) を満たす整数組 \((i,j)\) の個数．

操作を行うことで擬似転倒数が \(1\) 以上減少することがわかります．

そして実は，疑似転倒数が \(1\) ずつ減少するような操作列が構成できます．

具体的には次のようにします．

\(x=1,2,\cdots,N\) と動かしていきます． ある \(x\) について処理する際，\(Q_1,\cdots,Q_{x-1}\) の疑似転倒数は \(0\) になっているとします． \(i<x,\ Q_i-Q_x \geq K\) を満たす \(Q_i\) を列挙し，\(i_1,i_2,\cdots,i_s\) とおきます． あとは，\((i_s,x),(i_{s-1},i_s),\cdots,(i_1,i_2)\) の順で処理を行えば，\(1\) 回の操作ごとに疑似転倒数が \(1\) 減ることになります． また，同じ \((Q_i,Q_j)\) に対して \(2\) 度以上操作することがないことも明らかです．

以上の手順を素直に実装すれば \(O(N^2)\) 時間解法が得られます．

回答例(C++)