A2. Потерянная цивилизация (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии вы должны вычислить сумму значений по всем подотрезкам. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Определим алгоритм для генерации последовательности из $$$m+k$$$ целых чисел следующим образом:

  1. Сначала получите последовательность $$$x$$$ из $$$m$$$ целых чисел в качестве входных данных. Если $$$k=0$$$, немедленно завершите алгоритм и верните последовательность $$$x$$$.
  2. Затем выберите любой индекс $$$1 \le i \le |x|$$$ и вставьте $$$(x_i+1)$$$ сразу после элемента $$$x_i$$$.
  3. Если $$$x$$$ содержит ровно $$$m+k$$$ целых чисел, завершите выполнение и верните последовательность $$$x$$$. В противном случае вернитесь ко второму шагу.

Алиса знает, что этот алгоритм использовался древней цивилизацией для того, чтобы надежно скрыть свои секреты. Алиса хочет узнать знания, которые они хотели скрыть, но это не простая задача — вывести входные данные из выходных данных алгоритма.

Для последовательности $$$b$$$ из $$$n$$$ целых чисел определим $$$f(b)$$$ как длину наиболее короткой последовательности, которая может быть задана в качестве входных данных для алгоритма, генерирующего $$$b$$$.

Для заданной последовательности $$$a$$$ из $$$n$$$ целых чисел вычислите значение следующей суммы

$$$$$$\sum_{l=1}^n {\sum_{r=l}^n {f([a_l,a_{l+1},\ldots,a_r])}}$$$$$$

Другими словами, вы должны найти сумму $$$f(c)$$$ по всем подотрезкам$$$^{\text{∗}}$$$ $$$c$$$ из $$$a$$$.

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

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

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

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

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

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$300\,000$$$.

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

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

Пример
Входные данные
5
5
1 2 3 4 5
5
1 3 5 7 9
5
1 2 5 6 5
7
1 2 4 5 3 7 8
9
9 8 9 2 3 4 4 5 3
Выходные данные
15
35
25
60
78
Примечание

В первом наборе входных данных все подпоследовательности $$$a=[1,2,3,4,5]$$$ могут быть сгенерированы из последовательностей длины $$$1$$$.

Во втором наборе входных данных все подпоследовательности $$$a=[1,3,5,7,9]$$$ не могут быть сгенерированы из более коротких последовательностей, чем они сами.