Consider an arbitrary optimal solution. Let \(1 \leq p_1 < p_2 < \cdots < p_w \leq K\) be the indices of the terms that are among the first \(K\) terms in the initial state but not in the final state. Similarly, let \(K+1 \leq q_1 < q_2 < \cdots < q_w \leq N\) be the indices of the terms that are among the first \(K\) terms in the final state not in the initial state. This optimal solution obviously performs at least \(q_w-p_1\) operations. Additionally, there always exist \(1 \leq i,j \leq w\) such that \(p_i < q_j\) (or the score would never increase). Now, consider a solution that only exchanges those \(p_i\) and \(q_j\). It is optimally performed by moving the value at the position \(p_i\) to the position \(K\) and the value at the position \(p_j\) to the position \(K+1\), and then swapping the values at the positions \(K\) and \(K+1\), with \(q_j-p_i\) operations. This is not more than the minimum number of operations that must be performed by an optimal solution we considered above.

Therefore, we only need to consider the case \(w=1\) to find the optimal solution. That is, we want to find the pair \((i, j)\) that minimizes \((j-i)\) among the ones satisfying \(1 \leq i \leq K\), \(K+1 \leq j \leq N\), \(A_i<A_j\).

Let us sort the indices \(i\) in ascending order of the pair \((A_i,-i)\) and examine them in order. If the current \(i\) satisfies \(K+1 \leq i\), swapping \(A_j<A_i\) is a potential optimal solution, where \(j\) is the largest index \(i\) we have examined so far that satisfies \(i \leq K\). Among those candidates, the one with the minimum number of operations is the final answer.

Sorting is the bottleneck of this method, resulting in a total complexity of \(O(N \log N)\).

Sample submission (c++)