| Algo Cup 2025 by csspace.io (Финал) |
|---|
| Закончено |
Функция $$$f$$$ принимает на вход последовательность $$$a_1, a_2, \dots, a_n$$$ и возвращает последовательность $$$b_1, b_2, \dots, b_n$$$ той же длины по следующему правилу: элемент $$$b_i$$$ равен количеству элементов префикса длины $$$i$$$ последовательности $$$a$$$, равных $$$a_i$$$.
К примеру,
Последовательность чисел $$$x_1, x_2, \dots, x_n$$$ называется хорошей, если для неё существует такая последовательность $$$a$$$, что $$$f(a) = x$$$. Например, последовательность $$$x = [1, 2, 3, 1]$$$ — хорошая, а $$$x = [1, 2, 2]$$$ и $$$x = [1, 2, 4]$$$ — нет.
Для заданной последовательности $$$x_1, x_2, \dots, x_n$$$ определите количество её подотрезков, являющихся хорошими последовательностями. Другими словами, найдите количество пар целых чисел $$$(\ell, r)$$$ таких, что $$$1\le \ell \le r\le n$$$ и $$$x_\ell, x_{\ell+1}, \ldots, x_r$$$ является хорошей последовательностью.
Каждый тест состоит из нескольких наборов входных данных. Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$) — количество наборов входных данных. Далее следуют описания наборов данных в следующем формате.
Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \le n \le 1\,000\,000$$$) — длину последовательности $$$x$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_i \le n$$$) — элементы последовательности $$$x$$$.
Кроме того, сумма длин последовательностей по всем наборам входных данных не превышает $$$1\,000\,000$$$.
Для каждого набора входных данных выведите одно целое число — количество подотрезков последовательности $$$x$$$, являющихся хорошими последовательностями.
681 1 2 2 2 1 2 3101 1 1 1 1 1 1 1 1 155 4 3 2 1101 2 3 1 2 1 2 1 3 161 2 3 4 5 1151 1 2 1 2 2 3 2 1 2 3 3 2 1 2
955124718
В первом наборе входных данных существует $$$9$$$ хороших подотрезков:
Во втором наборе входных данных любой подотрезок является хорошим.
В третьем наборе входных данных существует всего один хороший подотрезок — $$$x_5 = [1]$$$.
| Название |
|---|


