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

Определим $$$\operatorname{MAD}$$$ (Максимальное Повторяющееся Значение) в массиве как наибольшее число, которое присутствует в массиве хотя бы дважды. Если нет такого числа, которое присутствует в массиве хотя бы дважды, значение $$$\operatorname{MAD}$$$ равно $$$0$$$.

Например, $$$\operatorname{MAD}([1, 2, 1]) = 1$$$, $$$\operatorname{MAD}([2, 2, 3, 3]) = 3$$$, $$$\operatorname{MAD}([1, 2, 3, 4]) = 0$$$.

Вам дан массив $$$a$$$ размера $$$n$$$. Изначально переменная $$$sum$$$ равна $$$0$$$.

Следующий процесс будет выполняться, пока все числа в массиве $$$a$$$ не станут равными $$$0$$$:

  1. Присвоить $$$sum := sum + \sum_{i=1}^{n} a_i$$$;
  2. Пусть $$$b$$$ — массив размера $$$n$$$. Присвоим $$$b_i :=\ \operatorname{MAD}([a_1, a_2, \ldots, a_i])$$$ для всех $$$1 \le i \le n$$$, затем присвоим $$$a_i := b_i$$$ для всех $$$1 \le i \le n$$$.

Найдите значение $$$sum$$$ после выполнения процесса.

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

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — количество наборов входных данных.

Для каждого набора входных данных:

  • Первая строка содержит целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — размер массива $$$a$$$;
  • Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — элементы массива.

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

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

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

Пример
Входные данные
4
1
1
3
2 2 3
4
2 1 1 2
4
4 4 4 4
Выходные данные
1
13
9
40
Примечание

В первом наборе входных данных, изначально $$$a=[1]$$$.

В первом цикле:

  1. Присвоим $$$sum := sum + a_1 = 0+1=1$$$;
  2. Присвоим $$$b_1 :=\ \operatorname{MAD}([a_1])=\ \operatorname{MAD}([1])=0$$$, затем присвоим $$$a_1 := b_1$$$.

После первого цикла, $$$a=[0]$$$ и процесс завершается. Значение $$$sum$$$ после процесса равно $$$1$$$.

Во втором наборе входных данных, изначально $$$a=[2,2,3]$$$.

После первого цикла, $$$a=[0,2,2]$$$ и $$$sum=7$$$.

После второго цикла, $$$a=[0,0,2]$$$ и $$$sum=11$$$.

После третьего цикла, $$$a=[0,0,0]$$$ и $$$sum=13$$$. После этого процесс завершается.

Финальное значение $$$sum$$$ равно $$$13$$$.