F. Арктическое приобретение
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка$$$^{\text{∗}}$$$ $$$a_1,a_2,\ldots,a_n$$$ длины $$$n$$$.

Интервал $$$[l,r]$$$ ($$$1\le l\le r\le n$$$) является зубчатым, если и только если он содержит 21435-подпоследовательность; то есть существуют целые числа $$$i_1,i_2,i_3,i_4,i_5$$$ такие, что $$$l\le i_1 \lt i_2 \lt i_3 \lt i_4 \lt i_5\le r$$$, и $$$a_{i_2} \lt a_{i_1} \lt a_{i_4} \lt a_{i_3} \lt a_{i_5}$$$.

Ваша задача — подсчитать, сколько из $$$\frac{n(n+1)}2$$$ интервалов являются зубчатыми.

$$$^{\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\le n\le10^6$$$) — длина перестановки.

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

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

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

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

Пример
Входные данные
5
5
2 1 4 3 5
10
10 3 5 2 1 4 9 8 6 7
15
3 9 15 6 11 10 5 13 12 7 4 8 14 1 2
12
10 7 12 5 4 1 2 9 3 8 6 11
30
22 30 7 17 4 13 26 28 24 20 2 11 27 21 5 19 9 10 23 14 1 25 6 8 3 18 29 12 16 15
Выходные данные
1
0
28
5
185
Примечание

В первом наборе входных данных единственной зубчатой подпоследовательностью является $$$[1,5]$$$, содержащая $$$[2,1,4,3,5]$$$ как подпоследовательность.

В третьем наборе входных данных подпоследовательность $$$[1,8]$$$ является зубчатой, потому что она содержит $$$[9,6,11,10,13]$$$ как подпоследовательность, которая является 21435-подпоследовательностью.