C. Задача из Усть-Катава
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана перестановка$$$^{\text{∗}}$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$.

Назовём подотрезок перестановки $$$p_l, p_{l + 1}, \ldots, p_r$$$ хорошим, если в перестановке $$$p$$$ не существует другого подотрезка такой же длины с таким же значением минимального элемента.

Найдите количество хороших подотрезков перестановки $$$p$$$.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

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

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

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

Во второй строке каждого набора входных данных содержится $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_{i} \leq n$$$).

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

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

Для каждого набора входных данных выведите в одной строке количество хороших подотрезков.

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

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

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

В третьем наборе входных данных подотрезки $$$[p_1, p_2]$$$ и $$$[p_2, p_3]$$$ не являются хорошими, так как у них одинаковая длина и одинаковое значение минимального элемента. Все остальные подотрезки являются хорошими.