E. Боевые дроиды
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Граф Дуку хочет отправить отряд дроидов на важное задание. Перед ним стоит шеренга из $$$n$$$ дроидов, пронумерованных от $$$1$$$ до $$$n$$$ слева направо. Граф решил выбрать в качестве отряда подотрезок этой шеренги. То есть, всех дроидов с номерами от $$$l$$$ до $$$r$$$ для некоторых $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$). Каждый дроид характеризуется своим AIQ — коэффициентом искусственного интеллекта. AIQ дроида номер $$$i$$$ равен $$$a_i$$$.

Дроиды, находящиеся в одном отряде, могут объединяться в более продвинутых дроидов. Если в отряде есть два дроида с одинаковым AIQ, равным $$$x$$$, они могут объединиться в одного дроида с AIQ равным $$$x + 1$$$.

Дуку хочет выбрать такой отряд, чтобы все дроиды из отряда могли, в результате нескольких объединений, стать одним дроидом. Помогите ему посчитать количество различных отрезков шеренги, которые он может выбрать в качестве искомого отряда.

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

В первой строке дано одно целое число $$$n$$$ — количество дроидов в шеренге ($$$1 \le n \le 200\,000$$$).

Во второй строке даны $$$n$$$ целых чисел $$$a_i$$$ — коэффициенты искусственного интеллекта роботов ($$$1 \le a_i \le 10^9$$$).

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

В единственной строке выведите одно целое число — количество отрезков шеренги, которые граф Дуку может выбрать в качестве желаемого отряда.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
15$$$n \le 100$$$первая ошибка
29$$$n \le 1\,000$$$1первая ошибка
36$$$n \le 5\,000$$$, $$$a_i \le 2$$$первая ошибка
410$$$n \le 5\,000$$$, $$$a_i \le 30$$$3первая ошибка
511$$$n \le 5\,000$$$1 – 4первая ошибка
68$$$n \le 50\,000$$$, $$$a_i \le 2$$$3первая ошибка
717$$$n \le 50\,000$$$, $$$a_i \le 30$$$3, 4, 6первая ошибка
819$$$n \le 50\,000$$$1 – 7первая ошибка
915$$$n \le 200\,000$$$1 – 8первая ошибка
Примеры
Входные данные
3
1 1 2
Выходные данные
5
Входные данные
7
3 4 3 5 3 4 3
Выходные данные
13
Примечание

В первом примере помимо трёх подходящих отрезков длины $$$1$$$, подходят отрезки $$$[1, 1]$$$ и $$$[1, 1, 2]$$$.

Во втором примере помимо семи подходящих отрезков длины $$$1$$$, подходят все четыре отрезка длины $$$4$$$, а также два отрезка $$$[3, 4, 3]$$$.