C. Безграничная странность массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ясину подарили массив a, состоящий из n целых чисел. Ясину только 5 лет, поэтому он любит разные странные вещи.

Ясин называет странностью массива максимум gcd(ai,  aj) по всем 1 ≤ i < j ≤ n. Для n ≤ 1 странность массива полагается равной 0. gcd(x,  y) означает наибольший общий делитесь целых чисел x и y.

Также он определяет безграничную странность массива. Безграничная странность равняется , где f(i,  j) равняется странности массива a, получаемого удалением всех элементов с i по j включительно, то есть массива [a1... ai - 1, aj + 1... an].

Поскольку Ясину только 5 лет, и программировать он не умеет, он просит вас помочь ему вычислить безграничную странность данного массива a.

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

В первой строке входных данных записано целое число n (1 ≤ n ≤ 200 000) — количество элементов в массиве a.

Далее следуют n целых чисел ai (1 ≤ ai ≤ 200 000), i-е из которых равно i-му элементу массива a. Гарантируется, что все числа ai различны.

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

Выведите одно целое число — безграничную странность массива a.

Пример
Входные данные
3
2 6 3
Выходные данные
6
Примечание

Рассмотрим первый пример.

  • f(1,  1) равняется 3.
  • f(2,  2) равняется 1.
  • f(3,  3) равняется 2.
  • f(1,  2), f(1,  3) и f(2,  3) равны 0.
Таким образом, ответ равен 3 + 0 + 0 + 1 + 0 + 2 = 6.