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

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

时间限制：$\mathtt{\text{2s}}$

空间限制：$\mathtt{\text{1024MB}}$

下载

样例数据下载