解説全体を通して，添え字に登場する \(0,N+1\) はそれぞれ \(N,1\) を指すものとします．

まず，明らかに \(\sum_{1 \leq i \leq N} A_i=0\) が必要です． 以下これを仮定します．

\(a_i\) を，操作で \(i\) を選んだ回数とします．

\(a_i\) の条件は，

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

です． \(b_i=a_{i+1}-a_i\) とおくと，二番目の条件は \(b_i-b_{i-1}=A_i\) となおせます．

これを見ると，すべての \(i\) について \(b_i-b_1\) の値がわかります． また定義より，\(\sum_{1 \leq i \leq N}b_i=0\) なので，これを用いると \(b_1\) の値を決定できます． ここで \(b_1\) の値が整数にならなければ，答えは不可能です．

\(b_i\) の値が分かったことで，すべての \(i\) について \(a_i-a_1\) の値を決定できます． ここでは \(a_1\) の選び方に自由度がありますが，\(a_i \geq 0\) がすべての \(i\) について満たされる，という条件の元で最小のものを取ればよいです．

計算量は全体で \(O(N)\) になります．