C. Максимизируйте счёт
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ длины $$$2n$$$. Каждое целое число от $$$1$$$ до $$$n$$$ встречается в $$$a$$$ ровно два раза.

Изначально ваш счёт равен $$$0$$$.

Пока массив $$$a$$$ не пуст, вы можете многократно выполнять следующую операцию:

  • Выберите целое число $$$x$$$, которое присутствует в $$$a$$$.
  • Пусть $$$l$$$ и $$$r$$$ — индексы самого левого и самого правого вхождения числа $$$x$$$ в текущем массиве соответственно. Если $$$x$$$ встречается только один раз, то $$$l = r$$$.
  • Прибавьте $$$(r - l + 1)^2$$$ к вашему счёту.
  • Удалите элементы $$$a_l, a_{l + 1}, \ldots, a_r$$$ из $$$a$$$. Оставшиеся элементы соединяются без изменения порядка и перенумеровываются, начиная с $$$1$$$.

Найдите максимальный возможный счёт после того, как массив станет пустым.

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

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

В первой строке каждого набора входных данных дано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Во второй строке даны $$$2n$$$ целых чисел $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1 \le a_i \le n$$$).

Гарантируется, что каждое целое число от $$$1$$$ до $$$n$$$ встречается в $$$a$$$ ровно два раза.

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

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

Для каждого набора входных данных выведите одно целое число — максимальный возможный счёт.

Пример
Входные данные
6
1
1 1
2
1 2 1 2
2
1 2 2 1
3
1 1 2 3 3 2
3
1 2 3 3 2 1
4
1 2 3 4 1 2 3 4
Выходные данные
4
10
16
20
36
28
Примечание

Во втором наборе входных данных один из оптимальных способов — сначала выбрать $$$x = 1$$$. Это удаляет подмассив $$$[1, 2, 1]$$$ и добавляет к счёту $$$3^2 = 9$$$. Оставшийся массив — $$$[2]$$$; выбор $$$x = 2$$$ добавляет $$$1$$$. Итого счёт равен $$$10$$$.

В третьем наборе входных данных выбор $$$x = 1$$$ удаляет весь массив и добавляет к счёту $$$4^2 = 16$$$.

В четвёртом наборе входных данных сначала выберите $$$x = 1$$$, а затем выберите $$$x = 2$$$. Итого получается $$$2^2 + 4^2 = 20$$$.

В шестом наборе входных данных сначала выберите $$$x = 2$$$. Это удаляет подмассив $$$[2, 3, 4, 1, 2]$$$ из середины массива и добавляет к счёту $$$5^2 = 25$$$. После удаления этого подмассива и объединения оставшихся элементов получается массив $$$[1, 3, 4]$$$. После этого выбор каждого из трёх оставшихся значений добавляет $$$1$$$, поэтому итоговый счёт равен $$$28$$$.