Let \(Q_k\) denote the permutation \(P\) after performing the operation with \(i=k\).

First, we determine whether there is an \(i\) such that \(Q_i=P\). This is equivalent to checking whether there is an \(i\) such that \(P_{i} < P_{i+1} < P_{i+2} < \dots < P_{i+K-1}\). This can be determined in \(O(N)\) time by using the cumulative sums of the counts of \(i\) with \(P_i < P_{i+1}\).

From here on, we consider the case with no \(i\) such that \(Q_i=P\).

Let’s consider \(Q_{N-K+1}\). This is obtained by sorting the last \(K\) terms of \(P\), so the first \(N-K\) terms remain as \((P_1,P_2,\dots,P_{N-K})\). Considering that \(Q_i\) cannot be lexicographically larger than \(P\), we can see that the lexicographically largest \(Q_i\) is the one where the first \(N-K\) terms remain as \((P_1,P_2,\dots,P_{N-K})\).

Let’s consider \(Q_i\) that satisfies this condition. First, when \(i+K-1 \leq N-K\), \(Q_i\) satisfies the above condition only when the \(K\) terms are sorted from the beginning, that is, when \(Q_i=P\) holds. By assumption, such an \(i\) does not exist.

Next, let’s consider the case where \(N-K+1 \leq i+K-1\). In this case, \(Q_i\) is obtained by sorting the part \(P_{i},P_{i+1},\dots,P_{N-K},P_{N-K+1},P_{N-K+2},\dots,P_{i+K-1}\). Thus, \(Q_i\) satisfies the above condition when:

• \(P_i < P_{i+1} < \dots < P_{N-K}\), and
• the minimum value of \(P_{N-K+1},P_{N-K+2},\dots,P_{i+K-1}\) is greater than \(P_{N-K}\).

The first condition can be determined by the cumulative sum as before, and the second can also be determined by pre-calculating the cumulative minimums of \(P_i\) from \(P_{n-K+1}\) onwards.

Additionally, for \(i\) that satisfies the conditions, \(Q_i\) is obtained by sorting the part \(P_{N-K+1},P_{N-K+2},\dots,P_{i+K-1}\), and the smaller \(i\) is, the shorter the part to be sorted, so we only need to consider the smallest \(i\) that satisfies them.

From the above, the candidates for the lexicographically smallest \(Q_i\) have been narrowed down to at most two: \(Q_{N-K}\) and \(Q_i\) for the smallest \(i\) such that:

• \(P_i < P_{i+1} < \dots < P_{N-K}\), and
• the minimum value of \(P_{N-K+1},P_{N-K+2},\dots,P_{i+K-1}\) is greater than \(P_{N-K}\).

Now, we can find the answer by actually sorting the \(K\) terms for each and comparing them.

The computational complexity is \(O(N)\) for the part narrowing down the candidates using cumulative sums and the like, and \(O(N\log N)\) for finding the narrowed down \(Q_i\), which is sufficiently fast.