Actually, it is possible to turn \(A\) into a non-decreasing sequence if and only if the following condition is satisfied.

• A non-decreasing sequence where the difference between the maximum and minimum values is at most \(1\) is called a good sequence. It is possible to turn \(A\) into a good sequence through the operations.

(Proof) Since a good sequence is non-decreasing, if we can make \(A\) into a good sequence, then we can make \(A\) into a non-decreasing sequence.

Conversely, suppose we can transform \(A\) into a non-decreasing sequence through the operations. After initially making \(A\) into a non-decreasing sequence, we can perform the following operations to transform \(A\) into a good sequence:

• Invariant: Initially, the sequence \((A_1)\) is a good sequence, and \(A\) is non-decreasing.
• For \(i = 2, 3, \dots, N\) in order, perform the following:
  • Invariant: \((A_1, A_2, \dots, A_{i-1})\) is a good sequence, and \(A\) is non-decreasing.
  • While \((A_1, A_2, \dots, A_i)\) is not a good sequence, perform the following operation:
    • There exists exactly one position \(j\) \((1 \leq j \leq i-1)\) such that adding \(1\) to \(A_j\) keeps \((A_1, A_2, \dots, A_{i-1})\) a good sequence. Here, perform the operation on \((j, i)\).
      • If one repeats the operation, eventually \((A_1, A_2, \dots, A_i)\) becomes a good sequence. Because \((A_1, A_2, \dots, A_i)\) will be a good sequence if \(A_{i-1}\) and \(A_i\) coincide, and each operation decreases the difference between \(A_{i-1}\) and \(A_i\) by \(1\) or \(2\), if a good sequence is not obtained, it would mean that we chose \(j = i - 1\) for the operation when the difference between \(A_{i-1}\) and \(A_i\) is \(1\). But in this case, \((A_1, A_2, \dots, A_{i-1}, A_i) = (x, x, \dots, x, x+1)\), which is already a good sequence, so the operation would not be performed.
  • After the operation, \((A_1, A_2, \dots, A_i)\) is a good sequence, and \(A_i \leq A_{i+1}\), so \(A\) remains non-decreasing.

Therefore, we have proved that the two propositions are equivalent. (End of Proof)

Whether it is possible to make \(A\) into a good sequence can be determined in \(\mathrm{O}(N)\) time using cumulative sums. Therefore, we can solve this problem in \(\mathrm{O}(N)\) per test case, which is sufficiently fast.