First, let’s show that we can always sort the permutation in 3 operations.
Let’s sort segments P[1:K], P[N-K+1:N], P[1:K] in this order. In order for the last operation to be successful, we just need to have P_i = i for all K+1 \le i \le N after the second operation. To get this, it’s sufficient and necessary for all integers from K+1 to N to be present in P[N-K+1:N] after the first operation. And they all will be: all integers from [K+1:N] which were in P[1:K] will form some suffix of P[1:K] after sorting this segment. There are at most N-K of them, so the position of the first such number will be at least K - (N-K) + 1 = 2K-N+1 \ge N-K+1, as 3K\ge 2N by the statement.
So, it’s enough to determine when is it possible to sort in 0, 1, 2 operations.
- 0 operations are enough only when the permutation is already sorted.
Now, let L be the smallest index for which P_L \neq L, and R be the largest index for which P_R \neq R.
-
1 operation is enough iff R-L+1 \le K. Indeed, if R-L+1 \le K, we can just sort segment P[L:R], otherwise we won’t change at least one of P_L, P_R.
-
Now, when are 2 operations enough? Let’s forget about elements from P[1:L-1] and P[R+1:N], as any operation leaves them in place. Now, as we can’t cover P_L and P_R with one operation, the segment for each operation has to contain L or R. Wlog the segment for the second operation contains R, so we can assume that in the second operation we sorted [R-K+1, R].
Then, we just need to have P_i = i for all i with L\le i \le R-K after the first operation. It’s optimal to sort segment [L, L+K-1] then, and check if all those elements were in place.
Shortly, we can check if 2 operations are enough in the following way: check if applying the operation to segments P[L:L+K-1], P[R-K+1:R] in some order makes the permutation sorted.