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

Вам дан массив из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$. Вам разрешено выполнить следующую операцию один раз.

  • Выберите целое число $$$x$$$ (которое может быть отрицательным), и для каждого значения $$$i$$$ $$$(1 \leq i \leq n)$$$ присвойте $$$a_i = a_i + x$$$.

Например, если $$$a = [1, 3, 4, 2]$$$, и вы выполните операцию с $$$x = 3$$$, то $$$a$$$ теперь равен $$$[4, 6, 7, 5]$$$.

Выведите максимальное возможное значение $$$\operatorname{MEX}(a)$$$$$$^{\text{∗}}$$$ после выполнения операции.

$$$^{\text{∗}}$$$$$$\operatorname{MEX}(a)$$$ определяется как наименьшее неотрицательное целое число, которое отсутствует в массиве. Например, $$$\operatorname{MEX}([1, 2, 0, 5])$$$ равно $$$3$$$, а $$$\operatorname{MEX}([1, 2, 4, 9])$$$ равно $$$0$$$.

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

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

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

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

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

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

Для каждого набора входных данных выведите максимальное возможное значение $$$\operatorname{MEX}(a)$$$ после выполнения операции.

Пример
Входные данные
6
1
4
5
0 1 1 2 3
2
1 1
4
4 2 3 6
5
2 4 1 0 -1
6
-1 1 2 3 5 6
Выходные данные
1
4
1
3
4
3
Примечание

Для первого набора входных данных выполнение операции с $$$x = -4$$$ делает $$$a = [0]$$$, и $$$\operatorname{MEX}([0]) = 1$$$.

Для второго набора входных данных $$$\operatorname{MEX}$$$ уже равен $$$4$$$, что является максимальным возможным значением, поэтому мы можем выполнить операцию с $$$x = 0$$$, что не изменит массив.