To begin with the conclusion, a monotonically non-decreasing sequence of non-negative integers \(A\) is a “good sequence” if and only if it satisfies the following conditions:

• Let the sequence \(Z\) be defined by \(Z_i = i\ (1 \leq i \leq K-1)\) and \(Z_{i} = K \times Z_{i-K+1}\). Then, \(A_i < Z_i\).
• There exists an integer \(i\ (1 \leq i \leq N-K+1)\) such that \(A_j < j\ (j=1,2,\dots,i-1)\) and \(A_{i} + A_{i+1} + \dots + A_{i+K-1} \leq K i - 1\).

Accepting this, for the optimization part, we can first change each \(A_i\) to \(\min(A_i, Z_i - 1)\). Then, we do a brute force for the \(i\) that satisfies the second condition. Using prefix sums and so on, it can be done in \(O(N)\) time.

Below, we will demonstrate that the above conditions are indeed necessary and sufficient. We prove sufficiency first, then necessity.

Sufficiency

First, perform the operation on the \(K\) terms starting at the \(i\)-th term. Then, we have \(A_i < i\), and the \(K\) terms starting at \(A_i\) have the same value. From here, apply the operation on the \(K\)-term segments starting at \((i-1)\)-th, \((i-2)\)-th, \(\dots\), \(1\)-st terms, in this order. Eventually, the first \(K\) terms of \(A\) become \(0\).

After that, we make the \((K+1)\)-th, \((K+2)\)-th, \(\dots\), \(N\)-th terms become \(0\) in this order. We use induction to show that if \(A_1,A_2,\dots,A_{i-1}\) are \(0\) and \(A_i < Z_i\), then the \(i\)-th term can also become \(0\) through operations on \(K\)-term blocks within the first \(i\) terms. First, by performing the operation on the block whose last position is \(i\), we get \(A_{i-K+1} = \left\lfloor \frac{Z_i - 1}{K} \right\rfloor\). From the recurrence definition of \(Z\), this is smaller than \(Z_{i-K+1}\). By the inductive hypothesis, it can become \(0\). The same reasoning applies to the \((i-K+2)\)-th, \(\dots\), \(i\)-th terms. This completes the argument for sufficiency.

Necessity

First, suppose there exists an index \(i\) with \(Z_i \leq A_i\). It is possible to show that no matter how you apply operations, there will still remain such an index \(i\) in the sequence afterward, considering the case \(A = (0,0,\dots,0,Z_i,Z_i,\dots,Z_i)\) through some calculations. Particularly, \(Z_i\) is at least \(1\), so it is impossible to make all elements \(0\). Hence, the first condition is necessary.

For the second condition, let \(S_i = A_1 + A_2 + \dots + A_{i-1}\). Define a sequence \(H = (H_1, H_2, \dots, H_N)\) by the recurrence

\[\displaystyle H_i = \max_{\max(i-K+1,1) \leq j \leq \min(i-1,N-K+1)} \lceil \frac{K \times H_j - (S_i - S_j)}{K-(i-j)} \rceil.\]

(Let \(C_1 = 1\).) It would be hard to grasp what it means, but the idea is that \(A_i\) represents the minimum value of \(A_i\) such that after an operation involving the \(i\)-th term for \(i\) with \(H_i \leq i\), there will be a \(j < i\) with \(H_j \leq j\).

Let \(i_0\) be the smallest \(i\) such that \(H_i \leq A_i\), and let \(i_1\) be the smallest \(i\) such that \(S_{i+K} - S_i < K \times H_i\). If \(i_0 < i_1\), then it can be shown from the aforementioned property of \(H\) that it is impossible to make all elements \(0\), similarly to the \(Z_i \leq A_i\) case. Also, if neither \(i_0\) nor \(i_1\) exists, once you perform at least one operation, \(H_i \leq A_i\) holds for some \(i\), so it is again impossible to make all elements \(0\).

Now consider computing \(H_i\) in ascending order. Once we discover \(i_1\) preceding \(i_0\), you do not need to compute further, so when computing \(H_i\), we may assume \(K \times B_{j} \leq S_{j+K} - S_j\) for \(j \leq i-K\). Also, we only need to do this for \(i \leq N-K+1\).

Here, it turns out that \(H_i=i\). Showing this completes the argument for necessity.

We use induction. The case \(i=1\) is clear.

Assume we have \(A_j < H_j = j\) for \(j < i\) and \(K \times H_j \leq S_{j+K} - S_j\) for \(j \leq i-K\). By the definition of \(H_i\),

\[\displaystyle H_i \geq \lceil \frac{K \times H_{i-1} - A_{i-1}}{K-1} \rceil = i + \lceil \frac{i-K - A_{i-1}}{K-1} \rceil.\]

From \(A_{i-1} < i-1\), we get \(H_i \geq i\).

To show \(H_i \leq i\), it suffices to show

\[\displaystyle \lceil \frac{K \times H_j - (S_i - S_j)}{K-(i-j)} \rceil \leq i \iff (S_i-S_j) \geq (i-j)(i-K).\]

Since \(A\) is monotonically non-decreasing, \(S_i\) is convex downward, so

\[\displaystyle \frac{S_i-S_j}{i-j} \geq \frac{S_i-S_{i-K}}{K} \geq i-K.\]

This completes the proof.