適当な最適解を考えます． 初期状態で \(A\) の先頭 \(K\) 項に含まれ，最終的に含まれないものの index を \(1 \leq p_1 < p_2 < \cdots < p_w \leq K\) と置きます． 同様に，初期状態で \(A\) の先頭 \(K\) 項に含まれず，最終的に含まれるものの index を \(K+1 \leq q_1 < q_2 < \cdots < q_w \leq N\) と置きます． この最適解の操作回数は明らかに \(q_w-p_1\) 回以上です． また，\(1 \leq i,j \leq w\) であって，\(p_i < q_j\) が成り立つものが必ず存在します（存在しなければスコアが増加するはずがないため）． ここで，そのような \(p_i,q_j\) だけを入れ替える解を考えてみます． 位置 \(p_i\) にある値を位置 \(K\) まで移動，位置 \(q_j\) にある値を位置 \(K+1\) まで移動，位置 \(K,K+1\) にある値を入れ替える，とするのが最適で，このときの操作回数は \(q_j-p_i\) になります． これは最初に考えてた最適解の操作回数以下です．

結局，最適解として考えるべきは，\(w=1\) のケースだけだとわかります． つまり，\(1 \leq i \leq K\)，\(K+1 \leq j \leq N\)，\(A_i<A_j\) を満たす \((i,j)\) の中で，\((j-i)\) が最小になるものを見つける問題です．

ペア \((A_i,-i)\) の昇順に \(i\) を並べ，順番に見ていきます． 今見ている \(i\) が \(K+1 \leq i\) ならば，今まで見た \(i\) のうち，\(i \leq K\) であるもののなかで最大となるものを \(j\) として，\(A_j<A_i\) の入れ替えが最適解の候補として挙がります． これらの候補の中で最も操作回数が少ないものが最終的な答えになります．

計算量はソート部分がボトルネックになり，全体で \(O(N \log N)\) です．

解答例(c++)