Граф Дуку хочет отправить отряд дроидов на важное задание. Перед ним стоит шеренга из $$$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$$$).
В единственной строке выведите одно целое число — количество отрезков шеренги, которые граф Дуку может выбрать в качестве желаемого отряда.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 5 | $$$n \le 100$$$ | первая ошибка | |
| 2 | 9 | $$$n \le 1\,000$$$ | 1 | первая ошибка |
| 3 | 6 | $$$n \le 5\,000$$$, $$$a_i \le 2$$$ | первая ошибка | |
| 4 | 10 | $$$n \le 5\,000$$$, $$$a_i \le 30$$$ | 3 | первая ошибка |
| 5 | 11 | $$$n \le 5\,000$$$ | 1 – 4 | первая ошибка |
| 6 | 8 | $$$n \le 50\,000$$$, $$$a_i \le 2$$$ | 3 | первая ошибка |
| 7 | 17 | $$$n \le 50\,000$$$, $$$a_i \le 30$$$ | 3, 4, 6 | первая ошибка |
| 8 | 19 | $$$n \le 50\,000$$$ | 1 – 7 | первая ошибка |
| 9 | 15 | $$$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]$$$.
