D. Мани и подпоследовательности
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Массив $$$b$$$ длины $$$|b|$$$ называется милым, если сумма длины его наибольшей возрастающей подпоследовательности (НВП) и длины его наибольшей убывающей подпоследовательности (НУП)$$$^{\text{∗}}$$$ ровно на один больше, чем длина массива. Более формально, массив $$$b$$$ милый, если $$$\operatorname{LIS}(b) + \operatorname{LDS}(b) = |b| + 1$$$.

Вам дана перестановка $$$a$$$ длины $$$n$$$$$$^{\text{†}}$$$. Ваша задача — подсчитать количество непустых подмассовов$$$^{\text{‡}}$$$ перестановки $$$a$$$, которые являются милыми.

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

Наибольшая возрастающая (убывающая) подпоследовательность — это самая длинная подпоследовательность, элементы которой расположены в строго возрастающем (убывающем) порядке.

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

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

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы перестановки $$$a$$$.

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

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

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

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

В первом наборе входных данных все $$$6$$$ непустых подмассивов являются милыми:

  • $$$[3]$$$: $$$\operatorname{LIS}([3]) + \operatorname{LDS}([3]) = 1 + 1 = 2$$$.
  • $$$[1]$$$: $$$\operatorname{LIS}([1]) + \operatorname{LDS}([1]) = 1 + 1 = 2$$$.
  • $$$[2]$$$: $$$\operatorname{LIS}([2]) + \operatorname{LDS}([2]) = 1 + 1 = 2$$$.
  • $$$[3, 1]$$$: $$$\operatorname{LIS}([3, 1]) + \operatorname{LDS}([3, 1]) = 1 + 2 = 3$$$.
  • $$$[1, 2]$$$: $$$\operatorname{LIS}([1, 2]) + \operatorname{LDS}([1, 2]) = 2 + 1 = 3$$$.
  • $$$[3, 1, 2]$$$: $$$\operatorname{LIS}([3, 1, 2]) + \operatorname{LDS}([3, 1, 2]) = 2 + 2 = 4$$$.

Во втором наборе входных данных одним из милых подмассивов является $$$[2, 3, 4, 5, 1]$$$, так как $$$\operatorname{LIS}([2, 3, 4, 5, 1]) = 4$$$ и $$$\operatorname{LDS}([2, 3, 4, 5, 1]) = 2$$$, что удовлетворяет условию $$$4 + 2 = 5 + 1$$$.