D. Сумма НУП
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана перестановка$$$^{\text{∗}}$$$ $$$p_1, \ldots, p_n$$$ такая, что $$$\max(p_i, p_{i+1}) \gt p_{i+2}$$$ для всех $$$1 \leq i \leq n-2$$$.

Вычислите сумму длин наибольшей убывающей подпоследовательности$$$^{\text{†}}$$$ подмассивов $$$[p_l, p_{l+1}, \ldots, p_r]$$$ для всех пар $$$1 \leq l \leq r \leq n$$$.

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

$$$^{\text{†}}$$$Для данного массива $$$b$$$ длины $$$|b|$$$, убывающая подпоследовательность длины $$$k$$$ — это последовательность индексов $$$i_1, \ldots, i_k$$$ такая, что:

  • $$$1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq |b|$$$
  • $$$b_{i_1} \gt b_{i_2} \gt \ldots \gt b_{i_k}$$$
Входные данные

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \leq n \leq 500\,000$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, $$$p_i$$$ попарно различны).

Гарантируется, что $$$\max(p_i, p_{i+1}) \gt p_{i+2}$$$ для всех $$$1 \leq i \leq n-2$$$.

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$500\,000$$$.

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

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

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

Для массива $$$a$$$ обозначим $$$\text{LDS}(a)$$$ как длину наибольшей убывающей подпоследовательности в $$$a$$$.

В первом наборе входных данных все подмассивы убывающие.

Во втором наборе мы имеем

$$$\text{LDS}([4]) = \text{LDS}([3]) = \text{LDS}([1]) = \text{LDS}([2]) = 1$$$

$$$\text{LDS}([4,3]) = \text{LDS}([3,1]) = 2, \text{LDS}([1, 2]) = 1$$$

$$$\text{LDS}([4,3,1]) = 3, \text{LDS}([3,1,2]) = 2$$$

$$$\text{LDS}([4,3,1,2]) = 3$$$

Таким образом, ответ равен $$$1+1+1+1+2+2+1+3+2+3=17$$$.