Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

D. Преобразование массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Функция $$$f$$$ принимает на вход последовательность $$$a_1, a_2, \dots, a_n$$$ и возвращает последовательность $$$b_1, b_2, \dots, b_n$$$ той же длины по следующему правилу: элемент $$$b_i$$$ равен количеству элементов префикса длины $$$i$$$ последовательности $$$a$$$, равных $$$a_i$$$.

К примеру,

  • если $$$a = [7, 7, 7, 1, 7, 4, 1]$$$, то $$$b = [1, 2, 3, 1, 4, 1, 2]$$$;
  • если $$$a = [1, 2, 1, 2, 1, 2]$$$, то $$$b = [1, 1, 2, 2, 3, 3]$$$;
  • если $$$a = [1, 2, 3, 3, 2, 1]$$$, то $$$b = [1, 1, 1, 2, 2, 2]$$$.

Последовательность чисел $$$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$$$, являющихся хорошими последовательностями.

Пример
Входные данные
6
8
1 1 2 2 2 1 2 3
10
1 1 1 1 1 1 1 1 1 1
5
5 4 3 2 1
10
1 2 3 1 2 1 2 1 3 1
6
1 2 3 4 5 1
15
1 1 2 1 2 2 3 2 1 2 3 3 2 1 2
Выходные данные
9
55
1
24
7
18
Примечание

В первом наборе входных данных существует $$$9$$$ хороших подотрезков:

  • $$$x_1 = [1]$$$;
  • $$$x_1, x_2 = [1, 1]$$$;
  • $$$x_1, x_2, x_3 = [1, 1, 2]$$$;
  • $$$x_1, x_2,x_3, x_4 = [1, 1, 2, 2]$$$;
  • $$$x_2 = [1]$$$;
  • $$$x_2, x_3 = [1, 2]$$$;
  • $$$x_6 = [1]$$$;
  • $$$x_6, x_7 = [1, 2]$$$;
  • $$$x_6, x_7, x_8= [1, 2, 3]$$$.

Во втором наборе входных данных любой подотрезок является хорошим.

В третьем наборе входных данных существует всего один хороший подотрезок — $$$x_5 = [1]$$$.