\(i=k\) として操作した後の \(P\) を \(Q_k\) と表記します。

まず \(Q_i=P\) なる \(i\) が存在するかを判定します。 \(P_{i} < P_{i+1} < P_{i+2} < \dots < P_{i+K-1}\) が成り立つ \(i\) が存在するかがわかればいいです。これは \(P_i < P_{i+1}\) が成り立つ \(i\) の個数を計算する累積和を用いることで \(O(N)\) で判定できます。

以降 \(Q_i=P\) なる \(i\) が存在しないようなケースについて考えます。

\(Q_{N-K+1}\) について考えます。これは \(P\) の後ろ \(K\) 項をソートしたものなので、前 \(N-K\) 項については \((P_1,P_2,\dots,P_{N-K})\) のままです。 \(Q_i\) は \(P\) より辞書式順序で大きくならないことを考えると、辞書式順序最大の \(Q_i\) は前 \(N-K\) 項が \((P_1,P_2,\dots,P_{N-K})\) のままであることがわかります。

この条件を満たす \(Q_i\) について考えます。まず \(i+K-1 \leq N-K\) のとき、\(Q_i\) が上記の条件を満たすのは \(K\) 項が最初からソートされている場合、すなわち \(Q_i=P\) が成り立つときです。仮定からこのような \(i\) は存在しません。

次に \(N-K+1 \leq i+K-1\) の場合を考えます。この場合 \(Q_i\) は \(P_{i},P_{i+1},\dots,P_{N-K},P_{N-K+1},P_{N-K+2},\dots,P_{i+K-1}\) の部分をソートしたものです。よって \(Q_i\) が上記の条件を満たすのは

• \(P_i < P_{i+1} < \dots < P_{N-K}\)
• \(P_{N-K+1},P_{N-K+2},\dots,P_{i+K-1}\) の最小値は \(P_{N-K}\) より大きい

を満たすときです。 \(1\) 番目の条件については最初と同じように累積和によって判定でき、 \(2\) 番目の条件も \(P_{N-K+1} \) 以降の \(P_i\) の累積minを求めておけば判定できます。

また、条件を満たす \(i\) について、 \(Q_i\) は \(P_{N-K+1},P_{N-K+2},\dots,P_{i+K-1}\) の部分をソートしたものになり、 \(i\) が小さければ小さいほどソートする部分の長さが短くなるので、条件を満たす最小の \(i\) だけ考えればいいです。

以上より辞書式順序最小となりうる \(Q_i\) は \(Q_{N-K+1}\) と

• \(P_i < P_{i+1} < \dots < P_{N-K}\)
• \(P_{N-K+1},P_{N-K+2},\dots,P_{i+K-1}\) の最小値は \(P_{N-K}\) より大きい

を満たす最小の \(i\) に対する \(Q_i\) の高々 \(2\) つに絞り込めたので、それぞれ \(K\) 項をソートして具体的に求めた後比較することで答えがわかります。

計算量は累積和などを利用して絞り込むパートは \(O(N)\) 、最後に絞り込んだ \(Q_i\) を求めるのは \(O(N\log N)\) で行うことができ、十分高速です。