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

Вам дан массив из $$$n$$$ целых неотрицательных чисел $$$a_1, a_2, \dots, a_n$$$.

Пусть $$$m$$$ — переменная, изначально равная $$$0$$$. Медуза выполняет следующую операцию $$$n$$$ раз:

  • выбрать индекс $$$i$$$ ($$$1 \leq i \leq |a|$$$) и удалить $$$a_i$$$ из $$$a$$$.
  • прибавить $$$\operatorname{MEX}(a)^{\dagger}$$$ к $$$m$$$.

Медуза хочет узнать минимально возможное конечное значение $$$m$$$ при оптимальном выполнении всех операций.

$$$^{\dagger}$$$ MEX (minimum excluded) массива — это наименьшее целое неотрицательное число, которое не принадлежит массиву.

Например:

  • MEX массива $$$[2,2,1]$$$ равен $$$0$$$, так как $$$0$$$ не принадлежит массиву.
  • MEX массива $$$[3,1,0,1]$$$ равен $$$2$$$, так как $$$0$$$ и $$$1$$$ принадлежат массиву, а $$$2$$$ - нет.
  • MEX массива $$$[0,3,1,2]$$$ равен $$$4$$$, так как $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$ принадлежат массиву, а $$$4$$$ - нет.
Входные данные

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 5000$$$) — размер массива.

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

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$5000$$$.

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

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

Пример
Входные данные
4
8
5 2 1 0 3 0 4 0
2
1 2
5
1 0 2 114514 0
8
0 1 2 0 1 2 0 3
Выходные данные
3
0
2
7
Примечание

В первом наборе исходных данных мы удаляем элементы из $$$a$$$ в следующем порядке: $$$[5,2,\color{red}{1},0,3,0,4,0] \to [5,2,0,3,\color{red}{0},4,0] \to [5,2,\color{red}{0},3,4,0] \to [5,2,3,4,\color{red}{0}] \to [5,2,\color{red}{3},4] \to [\color{red}{5},2,4] \to [\color{red}{2},4] \to [\color{red}{4}] \to [~]$$$. Значение $$$m$$$ будет равно $$$1+1+1+0+0+0+0+0=3$$$.