Tuż przed Chińskim Nowym Rokiem Miki znalazł na wieży zegarowej magnetofon. Urządzenie to nie tylko potrafi automatycznie powtarzać nagrania, ale może również służyć do obliczania największego wspólnego dzielnika wszystkich liczb w ciągu.

Sposób użycia maszyny jest następujący: na początku wprowadza się ciąg o długości $n$, gdzie $i$-ta liczba to $a_i$ ($1 \le i \le n$).

W każdym kroku Miki może wybrać dwie sąsiednie liczby $a_i, a_{i+1}$ i wrzucić do maszyny liczbę monet równą dokładnie sumie tych dwóch liczb, czyli $a_i + a_{i+1}$. Następnie maszyna automatycznie oblicza największy wspólny dzielnik tych dwóch liczb i zastępuje nimi te dwie sąsiednie liczby w ciągu. Operację tę powtarza się tak długo, aż w maszynie pozostanie tylko jedna liczba – będzie ona wynikiem.

Jak mówi przysłowie, bogata mysz, która nie chce zostać mechanikiem magnetofonów, nie jest dobrym matematykiem. Miki chce wiedzieć, jaka jest minimalna liczba monet, którą musi wydać, aby obliczyć wynik.

Wejście

Pierwsza linia zawiera liczbę całkowitą dodatnią $n$, oznaczającą długość ciągu.

Druga linia zawiera $n$ liczb całkowitych dodatnich $a_i$, oznaczających elementy ciągu.

Wyjście

Jedna linia zawierająca liczbę całkowitą, oznaczającą minimalną liczbę wydanych monet.

Przykład

Przykład 1

Wejście 1

7
33 33 66 6 66 22 22

Wyjście 1

260

Uwagi 1

Na początku ciąg to $[33, 33, 66, 6, 66, 22, 22]$.

Krok 1: scal $a_4, a_5$, otrzymujemy $[33, 33, 66, 6, 22, 22]$.

Krok 2: scal $a_4, a_5$, otrzymujemy $[33, 33, 66, 2, 22]$.

Krok 3: scal $a_3, a_4$, otrzymujemy $[33, 33, 2, 22]$.

Krok 4: scal $a_2, a_3$, otrzymujemy $[33, 1, 22]$.

Krok 5: scal $a_1, a_2$, otrzymujemy $[1, 22]$.

Krok 6: scal $a_1, a_2$, otrzymujemy $[1]$.

Całkowity koszt to $(6 + 66) + (6 + 22) + (66 + 2) + (33 + 2) + (33 + 1) + (1 + 22) = 260$.

Przykład 2

Patrz pliki z danymi przykładowymi.

Ograniczenia

Dla wszystkich danych wejściowych gwarantuje się, że $1\le n\le 2\times 10^5$ oraz $1\le a_i \le 10^{12}$.