春節前夕，米奇在鐘樓上撿到了一台復讀機，這台復讀機不僅可以自動復讀，還可以用來求一個數列中所有數的最大公約數。

這台機器的使用方法是這樣的，初始輸入一個長度為 $n$ 的數列，第 $i$ 個數為 $a_i$（$1 \le i \le n$）。

每次，米奇可以選擇相鄰的兩個數 $a_i, a_{i+1}$，並向機器中投入恰好為這兩個數的和的金幣，也即 $a_i + a_{i+1}$。然後，機器就會自動計算出這兩個數字的最大公因數，並用它替換這兩個相鄰的數，替換的位置為這兩個數的位置。反覆執行這個操作，直到機器中的數列只剩下一個數，這個數就是答案。

正所謂不想當復讀機修理工的有錢鼠不是好數學家，米奇想知道，至少使用多少個金幣，才能算出答案。

輸入格式

第一行一個正整數 $n$，表示數列的長度。

第二行 $n$ 個正整數 $a_i$，表示這個數列。

輸出格式

一行一個整數，表示最小使用的金幣數。

範例

範例 1

7
33 33 66 6 66 22 22

260

說明

一開始，序列為 $[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$。

範例 2

見範例資料下載。

子任務

對於所有資料，保證 $1\le n\le 2\times 10^5, 1\le a_i \le 10^{12}$。