春节前夕，米奇在钟楼上捡到了一台的复读机，这台复读机不仅可以自动复读，还可以用来求一个数列中所有数的最大公约数。

这台机器的使用方法是这样的，初始输入一个长度为 $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$。

样例二

见样例数据下载。

限制与约定

对于所有数据，保证 $1\le n\le 2\times 10^5, 1\le a_i \le 10^{12}$。

时间限制：$\texttt{2s}$

空间限制：$\texttt{1024MB}$

下载

样例数据下载