Let \(S=\sum_{1 \leq i \leq N} A_i\).

For now, we will focus on whether there is a sequence satisfying the conditions. Let us split the final sequence into blocks of lengths \(Q, K, K \cdots, K\). Here, let \(1 \leq Q \leq K\) so that the division is unique. Let \(P\) be the number of blocks.

First, for every block, all values in it must be different. Thus, it is necessary that \(A_i \leq P\) for every \(1 \leq i \leq N\). It is also necessary that there is at most \(Q\) indices \(i\) such that \(A_i =P\).

On the other hand, if these conditions are satisfied, there is a sequence satisfying the conditions. Below, we will show this fact by actually constructing the lexicographically smallest such sequence.

For each \(0 \leq i \leq N-1\), we will decompose the last \(N-i\) terms into blocks of length \(K\) each, and let \(Q_i\) and \(P_i\) be the length of the part that will be left, and the number of blocks, respectively. Particularly, \(Q_0=Q,P_0=P\).

The lexicographically smallest sequence that satisfies the condition can be obtained by the following procedure.

• Let \(ans=()\), to which we will append values.
• For each \(i=0,1,\cdots,N-1\), do the following.
  • (a): If there are \(Q_i\) values \(v\) such that \(A_v=P_i\), let \(m\) be the smallest such value that does not appear in the last \(K-1\) terms of \(ans\).
  • (b): Otherwise, let \(m\) be the smallest value satisfying \(A_v \geq 1\) that does not appear in the last \(K-1\) terms of \(ans\).
  • Append \(m\) to the end of \(ans\) and decrease \(A_m\) by \(1\).

In order for this procedure to terminate normally, the following must hold.

• (1): For each \(i\), \(\max A_v \leq P_i\) before doing the operation. Also, there are at most \(Q_i\) values \(v\) such that \(A_v=P_i\).
• (2): For each \(i\), there is at least one value that satisfies the condition, allowing \(m\) to be defined.

On the other hand, if the procedure exits normally, it obviously leads to the lexicographically smallest result. Thus, now we just need to show (1) and (2).

For (1), we can easily see that if it holds for \(i=x\), it also holds for \(i=x+1\). It does hold for \(i=0\), which completes the proof by induction.

Let us show (2). Assume that, at the point \(i=x\), there happens to be no candidate for \(m\).

• If it happens on (a): It means that the last \(K-1\) terms of \(ans\) contains all \(v\) such that \(A_v=P_i\). However, in such a case, (1) should have been violated already at the point \(i=x-(K-1)\), which is a contradiction.

• If it happens on (b): There are at most \(K-1\) values \(v\) such that \(A_v \geq 1\). Here, it follows from (1) that \(N-i \leq K-1\), and we can also see that \(P_i=1\). Eventually, it can be seen that this case falls into the above category (a).

Strictly speaking, we also need to consider the case the length of \(ans\) is less than \(K-1\), but we can apply the same argument to that case. This completes the proof of the validity of the procedure above.

A naive implementation of the procedure takes \(O(SN)\) time, which is fast enough.