$i$ を選んで操作する回数を $T_i$ とします．$A$ の要素を全て $x$ に揃えることを考えます．
操作を終了した際の $A$ を $A'$ とします．(例えば sample 1 の場合なら $A = (4, 7, 4), A' = (7, 7, 7)$ です．) ここで，$A'_i = A_i + T_i + T_{2i} + T_{3i} + \cdots$ です．$A'_i$ が全て $x$ になるように $T_i$ を定めることが必要です．$i = N, N - 1, \cdots, 1$ の順に $T_i$ を定めることを考えると，簡単に計算できます．(後ろから見る方針を思いつくルートとしては，後ろの要素は大きい $i$ を選ばないと変わらないので，後ろの方から帳尻を合わせると良さそうというものです．)
sample 2 の場合なら $A = (1, 3, 4, 5, 6)$ です．$T_5 = x - 6, T_4 = x - 5, T_3 = x - 4, T_2 = x - 3 - T_4 = 2, T_1 = x - T_5 - T_4 - T_3 - T_2 = -2x + 12$ となります．

ここで，$T_i$ は $x$ の一次式になります．実装上は $T_i = a_i x + b_i$ となる $a_i, b_i$ を配列で管理すると便利かと思います．
これの計算は $1$ つの $T_i$ あたり $O(N)$ かかるので $O(N^2)$ のように見えますが，実は $O(N \log N)$ で可能です．

• $T_i$ の計算には $\frac{N}{i}$ 回程度の計算が必要です．
• $\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{N} = O(\log N)$ のため，合計で $O(N \log N)$ 回の計算です．(キーワード: 調和級数)

実際に $x$ に揃えることができるかは $T_i = a_i x + b_i$ が非負であることが必要です．これは $1$ 次不等式の要領で解くことができます．

• $a_i x + b_i \geq 0$ は $a_i x \geq -b_i$ と変形できます．
• $a_i = 0$ ならば $b_i$ が非負，負の順にそれぞれ $x$ は任意の整数，解なしです．
• $a_i$ が $0$ でないなら両辺を $a_i$ で割れば良いです．ここで，$a_i$ が負の場合は不等号が逆になること，整数の範囲に変換する際のオフセットに気をつけてください．

これで，揃えることのできる $x$ の範囲が求まりました．そのような $x$ が存在しない場合は揃えられないので -1 が答えです． 例えば，sample 2 の場合なら範囲は $6 \leq x \leq 6$ となります．sample 3 の場合なら $x$ として取れる範囲がないので -1 が答えです．

後は $x$ として取ることのできる範囲内で $T_i$ の総和を最小化すれば良いです．これは $x - A_1$ になります．これは操作によらず $A_1$ の値は $1$ に増えるため $A'_1 = A_1 + T_1 + T_2 + \cdots + T_N = x$ となるためです．
したがって，$x$ として取れる最小の値から $A_1$ を引けば良いです．
これらは $O(N \log N)$ で計算可能で，十分高速です．

実装例 (C++)

sounansya 追記：

以下が \(A\) を全て \(\max A+21739130\) に合わせる必要のあるケースです：

94
1 500000000 673913043 760869565 826086956 847826086 869565217 891304347 913043478 913043478 934782608 934782608 934782608 956521739 956521739 956521738 956521739 956521739 978260869 978260869 978260869 978260869 978260870 978260869 978260869 978260869 978260869 978260869 978260869 978260869 978260869 999999999 999999999 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 999999999 999999999 999999999 999999999 999999999 999999999 999999999 999999999 999999999 999999999 999999999 999999999 999999999 999999999 999999999 999999999 999999999 999999999 999999999 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000