Углубившись в дикую местность, Жили и Джили обнаружили загадочную последовательность чисел. Каждый префикс этой последовательности имеет важные характеристики, известные как 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$$$.
Для каждого набора входных данных выведите на отдельной строке максимальную сумму.
550 0 0 0 020 151 1 1 1 061 1 4 5 1 411000000000
5413301000000000
В первом наборе входных данных, как бы вы ни переставили элементы $$$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$$$. Можно показать, что это оптимальное решение.
