Наибольший общий делитель (НОД) двух чисел может вычислен по формуле:НОД(a,b) = a, если b = 0;НОД(a,b) =НОД(b,a%b), если b > 0, где % — остаток от деления.

Наибольший общий делитель нескольких чисел вычисляется последовательным применением НОД к парам чисел:

НОД(a,b,c) =НОД(НОД(a,b),c)НОД(a) = a

Вам дана последовательность a1,a2,…,aN. Требуется подсчитать количество различных НОД подпоследовательностей ai,ai+1,…,aj (где 1 ≤ i ≤ j ≤ N) этой последовательности.

Формат ввода

Первая строка ввода содержит одно целое число N(1 ≤ N ≤ 500000). Вторая строка ввода содержит N целых чисел в диапазоне от 1 до 1018, разделенных пробелами —последовательность a1,a2,…,aN.

Формат вывода

Вывести одно целое число — количество различных значений среди gcd для всех непрерывных подпоследовательностей в заданной последовательности.

Пример 1

ВВОД

4
9 6 2 4

ВЫВОД

6

Пример 2

ВВОД

4
9 6 3 4

ВЫВОД

5

sevenfoldblood    1   13.12.2021 08:55    2