Let’s consider the inverse permutation \(Q\) of \(P\). In other words, \(Q_{P_i} = i\).

Rephrasing the operation with \(Q\) as the main focus, it becomes as follows:

• Choose \(i, j\) such that \(1 \leq i < j \leq N\) and \(Q_i - Q_j \geq K\). Here, the pair \((Q_i, Q_j)\) must not have been chosen before. Swap \(Q_i\) and \(Q_j\).

We define the pseudo-inversion count of \(Q\) (a term used only here) as follows:

• The number of integer pairs \((i, j)\) such that \(i < j\) and \(Q_i - Q_j \geq K\).

It can be seen that performing the operation decreases the pseudo-inversion count by at least \(1\).

In fact, it is possible to construct a sequence of operations that decreases the pseudo-inversion count by \(1\) each time.

Specifically, proceed as follows:

Iterate \(x = 1, 2, \cdots, N\). Assume that, when processing a certain \(x\), the pseudo-inversion count of \(Q_1, \cdots, Q_{x-1}\) is \(0\). Enumerate \(Q_i\) that satisfy \(i < x\) and \(Q_i - Q_x \geq K\), and denote them as \(i_1, i_2, \cdots, i_s\). Then, process \((i_s, x), (i_{s-1}, i_s), \cdots, (i_1, i_2)\) in this order. This way, the pseudo-inversion count decreases by \(1\) with each operation. It is also clear that the same pair \((Q_i, Q_j)\) will not be operated on more than once.

Straightforward implementation of the above steps yields an \(O(N^2)\) time solution.

Sample Solution (C++)