原案:vwxyz

\(A\) の要素をすべて \(x\) にできるとします。
\(i\) を選ぶ操作の回数を \(C_i\) とすると、これは \(x\) の一次式で表すことができます。
\(i=N,N-1,\dots,1\) の順に、\(C_i\) を \(x\) の一次式で表したときの係数を求めていくことにすると、\(C_i\) に影響を与えるのは \(C_{2i},C_{3i},\dots\) のみなので、全体で \(O(N\log{N})\) で計算できます。

\(C_i\) は \(0\) 以上なので \(x\) の範囲が絞られ、逆に \(C_i\) が \(0\) 以上になるように \(x\) を決めれば、\(A\) の要素をすべて \(x\) にすることができます。

この範囲に収まるような非負整数 \(x\) がなければ、答えは \(-1\) です。
範囲に収まるような非負整数 \(x\) が存在するとします。
操作によってどのような \(i\) を選んでも \(A_1\) には必ず \(1\) が足されるため、すべての要素を \(x\) にするために必要な操作回数は \(x-A_1\) です。
よって、その範囲内で最小の \(x\) を取ったときの \(x-A_1\) が求める答えです。