各 \(1\leq i\leq N\) に対して、\(i_t = i\) となる最大の \(t\) を \(t(i)\) と書くことにします。ただし、そのような \(t\) が存在しないときには \(t(i) = -1\) とします。

添字を適当に付け替えることで、以下の解説では \(t(1)\leq t(2)\leq \cdots \leq t(N)\) を仮定しておきます。特に、最後の操作は \(A_N\) に \(1\) を加えるものです。

◆ 解の絞り込み (1)

最適解に対して、次が成り立ちます。

1. 操作前には \(\min A = 1\) が成り立つ
2. 操作終了時点で、\(A_N-1\leq A_1\leq A_2\leq \cdots \leq A_N\) が成り立つ。

1 つめの性質は、\(\min A\geq 2\) を満たす数列 \(A\) から \(I\) が得られるとき、すべての \(A_i\) に \(-1\) を加えても同じ \(I\) を得ることが可能であることから分かります。

2 つめの性質を確認します。

まず、一度でも操作対象となった \(A_i\) に対して、操作終了時点で \(t(i) < t(j) \implies A_j-1\leq A_i\leq A_j\) となることが、帰納的に確認できます。

一度も操作対象とならない \(A_i\) については、操作終了時点で \(A_i = A_N-1\) であるとしてよいです。実際、最後の操作が \(A_N\) に対して行われることから \(A_i\geq A_N-1\) が必要ですし、逆に \(A_i = A_N-1\) としても \(A_i\) が操作対象としないまま同じ \(I\) を得ることができます。したがって、\(t(i) = -1\) であるような \(i\) に対しては \(A_i = A_N-1\) であるとしてよいです。

不等式の列 \(A_N-1\leq A_1\leq A_2\leq \cdots \leq A_N\) において、最左辺と最右辺の差は \(1\) です。したがって、これらの \(\leq\) のうち、ちょうどひとつが 「\(<\)」 、残り \(N-1\) 個が 「\(=\)」であることが分かります。ひとつめの性質と合わせて、最適解が高々 \(N\) 通りに絞り込めました。

◆ 解の絞り込み (2)

上述の \(N\) 通りのうちから、数列 \(I\) と矛盾しないものがどれかを調べましょう。

操作終了時点で成り立つ不等式 \(A_N-1\leq A_1\leq A_2\leq \cdots \leq A_N\) から、操作の各時点で最小値をとる \(A_j\) のひとつを決定することができます。実際、操作終了後との差分が最も大きな \(A_j\) のうち \(j\) が最も小さいものが、そのような \(A_j\) となります。

\(k\) 番目の操作対象が \(A_{i_k}\) であり、\(k\) 番目の操作を行う時点での最小値のひとつが \(A_{j_k}\) であるとき、この操作が問題文の条件に矛盾しない条件はその時点で \(A_{i_k} = A_{j_k}\) が成り立つこととなります。この条件に矛盾しないのが \(N\) 通りのうちどのようなものであるかも容易に記述できます（適当な区間を用いて表すことができます）。

解の候補 \(N\) 通りのうち操作列に矛盾しないものが確定できれば、あとは辞書順最小のものを出力すればよいですが、これも容易です。

以上をまとめて、本問題は、\(O(N + K)\) 時間で解くことができます。