In one operation, the maximum value among the elements of \(x\) increases by at most \(1\). Additionally, the sum of absolute differences of adjacent elements of \(x\) (\(=\sum_{1 \leq i \leq N-1} |x_i-x_{i+1}|+|x_N-x_1|\)) increases by at most \(2\).

Thus, if we let \(M=\max{A_i}\) and \(D=(\sum_{1 \leq i \leq N-1} |A_i-A_{i+1}|+|A_N-A_1|)/2\), we need at least \(\max(M,D)\) operations.

It turns out this lower bound is achievable, which we will show below.

Let us look at the sequence of operations backward and show that it is possible to do the operation on \(A\) once to decrease the value \(\max(M, D)\) by \(1\).

First, consider the case in which \(M>D\). Here, it can be verified that there is no \(i\) such that \(A_i=0\) (by making a circuit of \(0, \cdots, M, \cdots, 0\), we can see that \(M \leq D\), which is a contradiction). Thus, the objective can be achieved by decreasing the whole sequence \(A\) by \(1\).

Next, the case in which \(M<D\) can be handled by choosing a maximal segment consisting of \(M\) in \(A\) and decreasing that segment by \(1\).

What remains is the case in which \(M=D\). As we did in the \(M < D\) case, consider a maximal segment consisting of \(M\) in \(A\). If such a segment uniquely exists, decreasing that segment by \(1\) will decrease both \(M\) and \(D\) by \(1\). Let us consider the case with multiple such segments. It can be verified here that there is no \(i\) such that \(A_i=0\) (by making a circuit of \(0, \cdots, M, \cdots, (\) less than \(M\) \(), \cdots, M, \cdots, 0\), we can see that \(M<D\)). Thus, it can be seen that an operation choosing a minimal segment containing all \(M\)s will decrease both \(M\) and \(D\) by \(1\).

This completes the proof. A straightforward implementation will run in \(O(N)\) time.

Sample submission (c++)