B. Марья Ивановна нарушает самоизоляцию
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Марье Ивановне, самой активной бабушке двора, надоело сидеть дома. Она решила организовать обряд против коронавируса.

У неё есть $$$n$$$ подруг-бабушек (сама Марья Ивановна в это количество не входит). Бабушка с номером $$$i$$$ готова прийти на обряд при условии, если в момент её появления во дворе кроме неё там будет как минимум $$$a_i$$$ других бабушек. Обратите внимание, что бабушки могут приходить во двор одновременно. Формально, бабушка $$$i$$$ готова прийти, если количество бабушек пришедших ранее или одновременно с ней больше или равно $$$a_i$$$.

Бабушки собираются во дворе так.

  • Изначально во дворе находится только Марья Ивановна (то есть количество бабушек во дворе равно $$$1$$$). Все остальные $$$n$$$ бабушек пока сидят по домам.
  • На очередном шаге Марья Ивановна выбирает подмножество бабушек, ни одна из которых ещё не вышла во двор. Каждой из них она обещает, что когда бабушка выйдет, во дворе будет не менее $$$a_i$$$ других бабушек (включая Марью Ивановну). Марья Ивановна может звонить сразу нескольким соседкам. В таком случае выбранные бабушки выйдут во двор одновременно.
  • Вы не можете обманывать бабушек, то есть ситуация, когда $$$i$$$-я бабушка, после выхода во двор обнаружит, что сейчас во дворе строго меньше $$$a_i$$$ других бабушек (кроме неё самой, но включая Марью Ивановну), запрещена. Обратите внимание, что если несколько бабушек появились во дворе одновременно, то они каждая из них видит в том числе остальных в момент выхода.

Ваша задача — найти, какое максимальное количество бабушек (включая себя) Марья Ивановна может собрать во дворе для проведения обряда «обкуривания от Короны-Вируса». Ведь чем больше людей в одном месте во время карантина, тем эффективнее обряд!

Рассмотрим пример: если $$$n=6$$$ и $$$a=[1,5,4,5,1,9]$$$, то:

  • на первом шаге Марья Ивановна может позвать бабушек с номерами $$$1$$$ и $$$5$$$, каждая из них будет видеть двух бабушек в момент выхода во двор (заметим, что $$$a_1=1 \le 2$$$ и $$$a_5=1 \le 2$$$);
  • на втором шаге Марья Ивановна может позвать бабушек с номерами $$$2$$$, $$$3$$$ и $$$4$$$, каждая из них будет видеть пять бабушек в момент выхода во двор (заметим, что $$$a_2=5 \le 5$$$, $$$a_3=4 \le 5$$$ и $$$a_4=5 \le 5$$$);
  • бабушку номер $$$6$$$ позвать во двор не получится — следовательно, ответ на для такого примера равен $$$6$$$ (сама Марья Ивановна и еще $$$5$$$ суммарно вышедших бабушек).
Входные данные

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

Первая строка описания набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество бабушек (Марья Ивановна в это количество не входит).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2\cdot10^5$$$).

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

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

Для каждого набора входных данных выведите единственное целое число $$$k$$$ ($$$1 \le k \le n + 1$$$) — максимальное возможное количество бабушек во дворе.

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

В первом наборе входных данных примера Марья Ивановна на первом шаге может позвать всех бабушек. Тогда каждая из них увидит пять бабушек, когда выйдет. Иными словами, ни одна не уйдёт домой. Поэтому во дворе будет Марья Ивановна и пять других бабушек.

Во втором наборе входных данных примера никто не сможет находиться во дворе, поэтому Марья Ивановна останется там одна.

Третий набор входных данных примера подробно разобран выше.

В четвёртом тестовом случае Марья Ивановна на первом шаге может позвать бабушек с номерами $$$1$$$, $$$2$$$ и $$$3$$$. Если на втором шаге Марья Ивановна позовёт только $$$4$$$-ю или только $$$5$$$-ю, то когда эта бабушка выходила бы во двор, то она бы увидела четверых бабушек, то есть Марья Ивановна по отдельности позвать $$$4$$$-ю и $$$5$$$-ю не может. Если она позовёт сразу обеих — $$$4$$$-ю и $$$5$$$-ю, то когда они будут выходить, то увидят по $$$4+1=5$$$ бабушек. Несмотря на то, что $$$4$$$-ю бабушку это устраивает, $$$5$$$-ю — этот вариант не устраивает. Следовательно, позвать одновременно $$$4$$$-ю и $$$5$$$-ю Марья Ивановна тоже не может. То есть во дворе будет только Марья Ивановна и три бабушки из первого шага.