В канун Праздника Весны Микки нашел на часовой башне диктофон. Этот диктофон умеет не только автоматически повторять записи, но и вычислять наибольший общий делитель (НОД) всех чисел в последовательности.

Способ использования этого устройства следующий: изначально вводится последовательность длины $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

Выходные данные 1

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}$.