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

Дана перестановка $$$p$$$$$$^{\text{∗}}$$$ длины $$$n$$$.

Из каждого индекса $$$i$$$ за один шаг можно перейти:

  • в любой индекс $$$j \lt i$$$, или
  • в первый индекс $$$j \gt i$$$, для которого $$$p_j \gt p_i$$$ (если такой индекс существует).
Иными словами:
  • Всегда можно перейти в любую позицию слева.
  • Вправо можно перейти только в ближайшую позицию, значение в которой строго больше текущего.
Для каждой пары индексов $$$(i,j)$$$ обозначим через $$$f(i,j)$$$ минимальное количество шагов, необходимое, чтобы перейти из $$$i$$$ в $$$j$$$. Заметим, что если достичь $$$j$$$ из $$$i$$$ невозможно, то $$$f(i,j)=0$$$.

Вычислите:

$$$$$$\sum_{1 \le i,j \le n} f(i,j).$$$$$$

$$$^{\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 10^6$$$) — длину $$$p$$$.

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

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

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

Для каждого набора входных данных выведите одно целое число — значение $$$\sum\limits_{1 \le i,j \le n} f(i,j)$$$.

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

Для первого набора входных данных $$$f(1, 2) + f(2, 1) = 1 + 1 = 2$$$.

Для второго набора входных данных $$$f(1, 2) + f(2, 1) = 0 + 1 = 1$$$.

Для третьего набора входных данных $$$f(1, 2) + f(1, 3) + f(2, 1) + f(2, 3) + f(3, 1) + f(3, 2) = 1 + 0 + 1 + 0 + 1 + 1 = 4$$$.

Для четвёртого набора входных данных $$$f(1, 2) + f(1, 3) + f(2, 1) + f(2, 3) + f(3, 1) + f(3, 2) = 1 + 2 + 1 + 1 + 1 + 1 = 7$$$.