春节前夕，米奇在钟楼上捡到了一台的复读机，这台复读机不仅可以自动复读，还可以用来求一个数列中所有数的最大公约数。
这台机器的使用方法是这样的，初始输入一个长度为 $n$ 的数列，第 $i$ 个数为 $a_i$（$1 \le i \le n$）。
每次，米奇可以选择相邻的两个数 $a_i, a_{i+1}$，并向机器中投入恰好为这两个数的和的金币，也即 $a_i + a_{i+1}$。然后，机器就会自动计算出这两个数字的最大公因数，并用它替换这两个相邻的数，替换的位置为这两个数的位置。反复执行这个操作，直到机器中的数列只剩下一个数，这个数就是答案。
正所谓不想当复读机修理工的有钱鼠不是好数学家，米奇想知道，至少使用多少个金币，才能算出答案。
输入格式
第一行一个正整数 $n$，表示数列的长度。
第二行 $n$ 个正整数 $a_i$，表示这个数列。
输出格式
一行一个整数，表示最小使用的金币数。
样例一
input
7 33 33 66 6 66 22 22
output
260
explanation
一开始，序列为 $[33, 33, 66, 6, 66, 22, 22]$。
第一步，合并 $a_4, a_5$，得到 $[33, 33, 66, 6, 22, 22]$。
第二步，合并 $a_4, a_5$，得到 $[33, 33, 66, 2, 22]$。
第三步，合并 $a_3, a_4$，得到 $[33, 33, 2, 22]$。
第四步，合并 $a_2, a_3$，得到 $[33, 1, 22]$。
第五步，合并 $a_1, a_2$，得到 $[1, 22]$。
第六步，合并 $a_1, a_2$，得到 $[1]$。
总代价为 $(6 + 66) + (6 + 22) + (66 + 2) + (33 + 2) + (33 + 1) + (1 + 22) = 260$。
样例二
见样例数据下载。
限制与约定
| 子任务编号 | $n$ | 分值 |
|---|---|---|
| $1$ | $\le 500$ | $5$ |
| $2$ | $\le 1000$ | $15$ |
| $3$ | $\le 3000$ | $15$ |
| $4$ | $\le 3\times 10^4$ | $30$ |
| $5$ | $\le 2\times 10^5$ | $35$ |
对于所有数据，保证 $1\le n\le 2\times 10^5, 1\le a_i \le 10^{12}$。