F. MEX против MED
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$p_1, p_2, \ldots, p_n$$$ длины $$$n$$$ чисел $$$0, \ldots, n - 1$$$. Посчитайте количество подотрезков $$$1 \leq l \leq r \leq n$$$ этой перестановки, таких что $$$mex(p_l, p_{l+1}, \ldots, p_r) > med(p_l, p_{l+1}, \ldots, p_r)$$$.

$$$mex$$$ множества чисел $$$S$$$ — это минимальное неотрицательное целое число, которое не встречается в множестве $$$S$$$. Например:

  • $$$mex({0, 1, 2, 3}) = 4$$$
  • $$$mex({0, 4, 1, 3}) = 2$$$
  • $$$mex({5, 4, 0, 1, 2}) = 3$$$

$$$med$$$ множества чисел $$$S$$$ — это медиана множества, то есть элемент, который после сортировки элементов по неубыванию будет стоять на позиции номер $$$\left \lfloor{ \frac{|S| + 1}{2} } \right \rfloor$$$ (элементы массива нумеруются начиная с $$$1$$$ и здесь $$$\left \lfloor{v} \right \rfloor$$$ обозначает округление вниз до наибольшего целого числа, не большего $$$v$$$). Например:

  • $$$med({0, 1, 2, 3}) = 1$$$
  • $$$med({0, 4, 1, 3}) = 1$$$
  • $$$med({5, 4, 0, 1, 2}) = 2$$$

Последовательность из $$$n$$$ чисел называется перестановкой, если она содержит в себе все числа от $$$0$$$ до $$$n - 1$$$ ровно по одному разу.

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

В первой строке входных данных дано единственное целое число $$$t$$$ $$$(1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Далее следуют описания наборов входных данных.

В первой строке каждого набора входных данных содержится единственное целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — длина перестановки $$$p$$$.

Во второй строке каждого набора входных данных содержится ровно $$$n$$$ целых чисел: $$$p_1, p_2, \ldots, p_n$$$ ($$$0 \leq p_i \leq n - 1$$$) — элементы перестановки $$$p$$$.

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

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

Для каждого набора входных данных выведите в единственной строке ответ — количество подотрезков $$$1 \leq l \leq r \leq n$$$ этой перестановки, таких что $$$mex(p_l, p_{l+1}, \ldots, p_r) > med(p_l, p_{l+1}, \ldots, p_r)$$$.

Пример
Входные данные
8
1
0
2
1 0
3
1 0 2
4
0 2 1 3
5
3 1 0 2 4
6
2 0 4 1 3 5
8
3 7 2 6 0 1 5 4
4
2 0 1 3
Выходные данные
1
2
4
4
8
8
15
6
Примечание

В первом наборе входных данных есть один ровно один подотрезок и на нем $$$mex({0}) = 1 > med({0}) = 0$$$.

В третьем наборе входных данных на данных подотрезках $$$[1, 0]$$$, $$$[0]$$$, $$$[1, 0, 2]$$$ и $$$[0, 2]$$$ $$$mex$$$ большем чем $$$med$$$.

В четвертом наборе входных данных на данных подотрезках $$$[0, 2]$$$, $$$[0]$$$, $$$[0, 2, 1]$$$ и $$$[0, 2, 1, 3]$$$ $$$mex$$$ большем чем $$$med$$$.