B. Жили, Mex и Max
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Углубившись в дикую местность, Жили и Джили обнаружили загадочную последовательность чисел. Каждый префикс этой последовательности имеет важные характеристики, известные как mex и max. Переставляя элементы последовательности, можно создать особый вид магии.

Дан массив $$$a$$$, состоящий из $$$n$$$ целых неотрицательных чисел. Вы можете произвольно изменять порядок элементов в массиве.

Найдите максимально возможное значение суммы MEX$$$^{\text{∗}}$$$ и максимумов по всем префиксам. Формально вам нужно максимизировать следующее выражение: $$$\sum\limits_{i=1}^n (\operatorname{mex}(a_1,a_2,\cdots,a_i)+\max(a_1,a_2,\cdots,a_i))$$$.

$$$^{\text{∗}}$$$Наименьшее исключенное (MEX) набора чисел $$$c_1, c_2, \ldots, c_k$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе чисел $$$c$$$.

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

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\cdots,a_n$$$ ($$$0\leq a_i \leq 10^9$$$) — массив $$$a$$$.

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

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

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

Пример
Входные данные
5
5
0 0 0 0 0
2
0 1
5
1 1 1 1 0
6
1 1 4 5 1 4
1
1000000000
Выходные данные
5
4
13
30
1000000000
Примечание

В первом наборе входных данных, как бы вы ни переставили элементы $$$a$$$, значения MEX и максимума для каждого префикса всегда будут равны $$$1$$$ и $$$0$$$ соответственно.

В третьем наборе входных данных можно переставить элементы $$$a$$$ в последовательность $$$[0,1,1,1,1]$$$, так что $$$\sum\limits_{i=1}^n (\operatorname{mex}(a_1,a_2,\cdots,a_i)+\max(a_1,a_2,\cdots,a_i))=(1+0)+(2+1)+(2+1)+(2+1)+(2+1)=13$$$. Можно показать, что это оптимальное решение.