Задача №114817. Подготовка тестов
Коля готовится к проведению олимпиады. До тура осталось не так много времени, а Коля все еще не сделал тесты к одной из задач. Поскольку времени на подготовку осталось мало, Коля принял взвешенное решение — сделать в этой задаче мультитест: несколько тестов, перечисленных один за другим во входных данных.
Каждый тест в этой задаче должен начинаться с числа \(m\), а далее содержать \(m\) пар целых неотрицательных чисел \(a_i\) и \(b_i\). Эти пары чисел задают ребра в неориентированном графе, вершины которого пронумерованы целыми числами от \(0\) до бесконечности. Граф во вводе не должен иметь петель и кратных рёбер, а также должен являться лесом — графом, не содержащим циклов.
Упростив себе задачу, он тем не менее не решил вопрос, где взять столько тестов. Тогда он вспомнил, что недавно уже делал задачу, входные данные к которой представляли собой массив целых неотрицательных чисел. Он решил выбрать отрезки подряд идущих элементов этого массива в качестве тестов к новой задаче.
Теперь его интересует вопрос — сколько различных подотрезков массива являются корректными тестами? Два подотрезка считаются различными, если у них не совпадают границы.
В первой строке дано одно целое число \(n\) — длина массива (\(1 \le n \le 300\,000\)).
Во второй строке даны \(n\) целых чисел \(a_i\) — массив (\(0 \le a_i \le 10^9\)).
Выведите одно целое число — количество различных подотрезков массива, которые являются корректными тестами для задачи.
В первом тесте корректными являются следующие подотрезки (выделены квадратными скобками):
- [2 1 3 4 1]
- 2 [1 3 4] 1
Во втором тесте корректными являются следующие подотрезки:
- [1 3 1] 2 2 0 2 3
- 1 [3 1 2 2 0 2 3]
- 1 3 1 [2 2 0 2 3]
- 1 3 1 2 2 [0] 2 3
- [1 3 1 2 2 0 2 3]
5 2 1 3 4 1
2
8 1 3 1 2 2 0 2 3
5