Statement is not available in English language
E. Самолеты-самолеты
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Самолеты-самолеты-самолеты. Тут нет самолетов, но зато есть интересная задача, которую предлагаем вам решить.

Дан массив $$$a_1, a_2, \ldots, a_n$$$. Отрезок $$$l, r$$$ ($$$1 \leq l \leq r \leq n$$$) называется хорошим, если выполняется следующее условие:

Для каждого $$$i$$$ от $$$1$$$ до $$$r - l + 1$$$ найдется такое $$$j$$$ ($$$l \leq j \leq r$$$), что $$$a_j = x^i$$$ для какого-то целого числа $$$x$$$.

Требуется сказать, сколько существует хороших отрезков.

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

В первой строке записано единственное число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — длина массива.

Во второй строке записано $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — сам массив.

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

Выведите единственное целое число — ответ на задачу.

Примеры
Входные данные
4
1 2 3 4
Выходные данные
8
Входные данные
5
2 3 4096 5 7
Выходные данные
12
Примечание

В первом тестовом примере подойдут пары $$$(l, r)$$$: $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(1, 4)$$$, $$$(2, 2)$$$, $$$(3, 3)$$$, $$$(3, 4)$$$, $$$(4, 4)$$$.