For each \(1\leq i\leq N\), let \(t(i)\) denote the largest \(t\) such that \(i_t = i\). If there is no such \(t\), let \(t(i) = -1\).

By reindexing the sequence, we assume \(t(1)\leq t(2)\leq \cdots \leq t(N)\) below. Particularly, the last operation adds \(1\) to \(A_N\).

◆ Narrowing down the candidates (1)

For an optimal solution, the following holds.

1. \(\min A = 1\) before the operations.
2. \(A_N-1\leq A_1\leq A_2\leq \cdots \leq A_N\) after the operations.

The first property can be seen from the following fact: when \(I\) can be obtained from a sequence \(A\) such that \(\min A\geq 2\), it can also be obtained after adding \(-1\) to all \(A_i\).

Let us verify the second property.

First, for \(A_i\) that becomes the target of an operation at least once, it can be inductively seen that \(t(i) < t(j) \implies A_j-1\leq A_i\leq A_j\) at the end of the process.

For \(A_i\) that never becomes the target of an operation, we can assume that \(A_i = A_N-1\) at the end of the process. Actually, since the last operation is done on \(A_N\), it is necessary that A_i\geq A_N-1\(. On the other hand, if we let \)A_i = A_N-1\(, the same \)I\( can be obtained without \)A_i\( being targetted by an operation. Thus, for \)i\( such that \)t(i) = -1\(, we can assume \)A_i = A_N-1$.

In the sequence of inequalities \(A_N-1\leq A_1\leq A_2\leq \cdots \leq A_N\), the difference between the leftmost and rightmost sides is \(1\). Thus, among those \(\leq\)’s, exactly one is \(<\) and the other \(N-1\) are \(=\). This, in addition to the first property, narrows down the candidates for the optimal solution to \(N\).

◆ Narrowing down the solutions (2)

Let us examine which of the above \(N\) candidates are consistent with the sequence \(I\).

From the inequality \(A_N-1\leq A_1\leq A_2\leq \cdots \leq A_N\) that holds at the end of the process, we can determine one of the \(A_j\)’s that takes the minimum value at each stage of the process. Actually, that is the smallest \(j\) with the greatest difference between the current and last values of \(A_j\).

If the \(k\)-th operation targets \(A_{i_k}\), and one of the smallest values just before the \(k\)-th operation is \(A_{j_k}\), the condition for this operation to be consistent with the specifications in the statement is \(A_{i_k} = A_{j_k}\). It is easy to state which of the \(N\) candidates are consistent with this condition (using some intervals).

After determining which of the \(N\) candidates are consistent with the sequence of operations, we just need to print the lexicographically smallest among them, which is easy.

From all of the above, the problem can be solved in \(O(N + K)\) time.