B2. Сортировка подотрезков (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственная разница между простой и сложной версиями состоит в ограничениях на $$$t$$$ и $$$n$$$.

Вам задан массив $$$a$$$, состоящий из $$$n$$$ различных целых чисел $$$a_1, a_2, \ldots, a_n$$$.

Определим стоимость массива $$$p_1, p_2, \ldots p_k$$$ как минимальное количество времени, необходимое для сортировки этого массива с использованием произвольного количества операций сортировки диапазона. В каждой операции сортировки диапазона вы будете делать следующее:

  • Выберите два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l < r \le k$$$).
  • Отсортируйте подмассив $$$p_l, p_{l + 1}, \ldots, p_r$$$ за $$$r - l$$$ секунд.

Пожалуйста, посчитайте сумму стоимостей по всем подмассивам массива $$$a$$$.

Подмассив массива определяется как непрерывная последовательность элементов массива.

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

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

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

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

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

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

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

Пример
Входные данные
5
2
6 4
3
3 10 6
4
4 8 7 2
5
9 8 2 4 6
12
2 6 13 3 15 5 10 8 16 9 11 18
Выходные данные
1
2
8
16
232
Примечание

В первом наборе входных данных:

  • Подмассив $$$[6]$$$ уже отсортирован, поэтому его стоимость равна $$$0$$$.
  • Подмассив $$$[4]$$$ уже отсортирован, поэтому его стоимость равна $$$0$$$.
  • Подмассив $$$[6, 4]$$$ можно отсортировать за одну операцию, выбрав $$$l = 1$$$ и $$$r = 2$$$. Его стоимость равна $$$1$$$.
Сумма стоимостей по всем подмассивам данного массива равна $$$0 + 0 + 1 = 1$$$.

Во втором наборе входных данных:

  • Подмассив $$$[3]$$$ уже отсортирован, поэтому его стоимость равна $$$0$$$.
  • Подмассив $$$[10]$$$ уже отсортирован, поэтому его стоимость равна $$$0$$$.
  • Подмассив $$$[6]$$$ уже отсортирован, поэтому его стоимость равна $$$0$$$.
  • Подмассив $$$[3, 10]$$$ уже отсортирован, поэтому его стоимость равна $$$0$$$.
  • Подмассив $$$[10, 6]$$$ можно отсортировать за одну операцию, выбрав $$$l = 1$$$ и $$$r = 2$$$. Его стоимость равна $$$2 - 1 = 1$$$.
  • Подмассив $$$[3, 10, 6]$$$ можно отсортировать за одну операцию, выбрав $$$l = 2$$$ и $$$r = 3$$$. Его стоимость равна $$$3 - 2 = 1$$$.
Сумма стоимостей по всем подмассивам данного массива равна $$$0 + 0 + 0 + 0 + 1 + 1 = 2$$$.