C. 23 королевство
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Расстояние значения $$$x$$$ в массиве $$$c$$$, обозначаемое как $$$d_x(c)$$$, определяется как наибольший промежуток между любыми двумя вхождениями $$$x$$$ в $$$c$$$.

Формально, $$$d_x(c) = \max(j - i)$$$ для всех пар $$$i \lt j$$$, где $$$c_i = c_j = x$$$. Если $$$x$$$ появляется только один раз или вовсе отсутствует в $$$c$$$, то $$$d_x(c) = 0$$$.

Красота массива — это сумма расстояний каждого уникального значения в массиве. Формально, красота массива $$$c$$$ равна $$$\sum\limits_{1\le x\le n} d_x(c)$$$.

Дан массив $$$a$$$ длины $$$n$$$. Массив $$$b$$$ является приятным, если он также имеет длину $$$n$$$ и его элементы удовлетворяют условию $$$1\le b_i\le a_i$$$ для всех $$$1\le i\le n$$$. Ваша задача — найти максимальную возможную красоту приятного массива.

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

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

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

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

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

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

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

Пример
Входные данные
4
4
1 2 1 2
2
2 2
10
1 2 1 5 1 2 2 1 1 2
8
1 5 2 8 4 1 4 2
Выходные данные
4
1
16
16
Примечание

В первом наборе входных данных, если $$$b = [1, 2, 1, 2]$$$, то $$$d_1(b) = 3 - 1 = 2$$$ и $$$d_2(b) = 4 - 2 = 2$$$, что приводит к красоте $$$2 + 2 = 4$$$. Можно показать, что нет приятных массивов с красотой больше $$$4$$$.

Во втором наборе входных данных как $$$b = [1, 1]$$$, так и $$$b = [2, 2]$$$ являются допустимыми решениями с красотой $$$1$$$.

В третьем наборе входных данных, если $$$b = [1, 2, 1, 4, 1, 2, 1, 1, 1, 2]$$$, то $$$d_1(b) = 9 - 1 = 8$$$, $$$d_2(b) = 10 - 2 = 8$$$, и $$$d_4(b) = 0$$$, что приводит к красоте $$$16$$$.