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

Массив $$$b$$$ из $$$m$$$ целых чисел называется хорошим, если после его сортировки выполняется $$$b_{\left\lfloor \frac{m + 1}{2} \right\rfloor} = b_{\left\lceil \frac{m + 1}{2} \right\rceil}$$$. Другими словами, $$$b$$$ является хорошим, если обе его медианы равны. В частности, если $$$m$$$ нечетно, то $$$\left\lfloor \frac{m + 1}{2} \right\rfloor = \left\lceil \frac{m + 1}{2} \right\rceil$$$, поэтому $$$b$$$ гарантированно будет хорошим, если он имеет нечетную длину.

Вам дан массив $$$a$$$ из $$$n$$$ целых чисел. Вычислите количество хороших подмассивов$$$^{\text{∗}}$$$ в $$$a$$$.

$$$^{\text{∗}}$$$Массив $$$x$$$ является подмассивом массива $$$y$$$, если $$$x$$$ может быть получен из $$$y$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длина массива.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le \color{red}{\textbf{10}}$$$) — заданный массив.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество хороших подмассивов в $$$a$$$.

Пример
Входные данные
3
4
1 1 1 1
5
1 10 2 3 3
10
6 3 2 3 5 3 4 2 3 5
Выходные данные
10
11
42
Примечание

В первом наборе входных данных каждый подмассив является хорошим, поскольку все его элементы равны $$$1$$$.

Во втором наборе входных данных примером хорошего подмассива является $$$b = [10, 2, 3, 3]$$$. Если его отсортировать, то $$$b = [2, 3, 3, 10]$$$, значит, $$$b_{\left\lfloor \frac{4 + 1}{2} \right\rfloor} = b_{\left\lceil \frac{4 + 1}{2} \right\rceil} = b_2 = b_3 = 3$$$. Другим примером может быть $$$b = [1, 10, 2]$$$. С другой стороны, $$$b = [1, 10]$$$ не подходит, поскольку его две медианы равны $$$1$$$ и $$$10$$$, и они не равны.