まず，\(x=A_N,A_{N-1},\ldots,A_1\) と操作することで，すべての値が \(0\) になります． よって，答えは \(A_1\) 以上です．

答えが \(A_1+1\) 以上だとします． この時，\(A_1\) の値は常に一定なので，その他すべての値を \(A_1\) に合わせることが目標になります．

もし，すべての \(i\) (\(2 \leq i \leq N\)) について \(A_i-A_{i-1} \geq A_1+1\) だった場合，\(x=A_i-A_1\) (\(i=N,N-1,\ldots,2\)) と操作することで，すべての値を \(A_1\) にできます． この時 \(x\) の最小値は \(A_2-A_1\) になるわけですが，これがそのまま答えになります． なぜなら，\(A_2-A_1+1\) 以上の操作しか行わない場合，\(A_2\) の値が減るような操作に注目すると，減ったあとの値が \(A_1-1\) 以下になってしまい，全部 \(A_1\) にするという目標が不可能になるからです．

最後に，ある \(i\) が存在して \(A_i-A_{i-1} \leq A_1\) となるケースを考えます． 一般に，ある \(2\) つの値 \(a,b\) (\(a<b\)) があり，\(1 \leq b-a \leq A_1\) だとします． \(A_1+1\) 以上の整数 \(x\) で操作を行ったとします． \(a,b\) をそれぞれ \(x\) で割った商を考えてみます． この \(2\) つの商が同じ場合，\(a,b\) を \(x\) で割ったあまりの差を考えると，それらは \(b-a\) と変わりません． よって，\(a,b\) の値が同じになるためには，いつかは \(2\) つの商が異なるような操作が起きるべきです． しかし \(2\) つの商が異なる場合，\(b\) を \(x\) で割ったあまりは \(A_1-1\) 以下になります． すると，\(b\) を \(A_1\) に合わせることは不可能になります． よって，結局答えは \(A_1\) だとわかります．

以上の結論をそのまま実装すれば，\(O(N)\) でこの問題は解けます．

回答例(C++)