Problem description

Jasio gra w grę Usuwanka. Gra polega na usunięciu ciągu liczb jak najtańszym kosztem. Ciąg jest cykliczny (można sobie wyobrażać, że jest zapisany na kółku), więc obok pierwszej liczby jest druga oraz ostatnia.

Jasio może usunąć dowolną liczbę z tego ciągu – kosztuje go to jednak tyle bajtalarów ile wynosi największy wspólny dzielnik bezpośrednich sąsiadów usuwanej liczby. Na przykład: dla ciągu (2,3,4,5), jeśli Jasio usunie 3, będzie go to kosztowało 2 bajtalary (największy wspólny dzielnik liczb 2 oraz 4). Jasio wykonuje takie operacje dopóki pozostaną mu tylko dwie liczby – usunięcie ich obu kosztuje wówczas tyle co ich największy wspólny dzielnik. Łatwo zauważyć, że kolejność usuwania liczb ma znaczenie dla łącznego kosztu. Jak nietrudno się domyślić, Jasio chciałby usunąć wszystkie liczby najtaniej. Pomóż mu!

Napisz program, który: wczyta ciąg liczb do usunięcia, wyznaczy optymalny sposób jego usunięcia i wypisze koszt usuwania na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca długość ciągu. W drugim (ostatnim) wierszu wejścia znajduje się ciąg N liczb naturalnych A_i, pooddzielanych pojedynczymi odstępami. Są to kolejne wyrazy (cyklicznego) ciągu Jasia.

Wyjście

W pierwszym (jedynym) wierszu wyjścia wypisać należy optymalny koszt usunięcia ciągu.

Ograniczenia

2 ≤ N ≤ 100, 1 ≤ A_i ≤ 1 000.

Przykład

4
2 3 4 5

3