Задача №114882. Боевые дроиды
Граф Дуку хочет отправить отряд дроидов на важное задание. Перед ним стоит шеренга из \(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 | первая ошибка |
В первом примере помимо трёх подходящих отрезков длины \(1\), подходят отрезки \([1, 1]\) и \([1, 1, 2]\).
Во втором примере помимо семи подходящих отрезков длины \(1\), подходят все четыре отрезка длины \(4\), а также два отрезка \([3, 4, 3]\).
3 1 1 2
5
7 3 4 3 5 3 4 3
13