Throughout this editorial, assume that \(0\) and \(N+1\) as indices stand for \(N\) and \(1\), respectively.

First, it is clearly necessary that \(\sum_{1 \leq i \leq N} A_i=0\). Below, we assume this to hold.

Let \(a_i\) be the number of times \(i\) is chosen in the operations.

The conditions for \(a_i\) are:

• \(a_i \geq 0\)
• \(2a_i-a_{i-1}-a_{i+1}=-A_i\)

By letting \(b_i=a_{i+1}-a_i\), the second condition can be converted into \(b_i-b_{i-1}=A_i\).

From this, we can determine the value \(b_i-b_1\) for every \(i\). Also, it follows from the definition that \(\sum_{1 \leq i \leq N}b_i=0\), which we can use to determine the value \(b_1\). If this value \(b_1\) is not an integer, there is no solution.

After finding out the values \(b_i\), we can determine the value \(a_i-a_1\) for every \(i\). Here, there is a degree of freedom in choosing \(a_1\), and we should choose the minimum value possible under the condition that \(a_i \geq 0\) holds for every \(i\).

The complexity is \(O(N)\) in total.