Codeforces Round 645 (Div. 2) |
---|
Закончено |
Марье Ивановне, самой активной бабушке двора, надоело сидеть дома. Она решила организовать обряд против коронавируса.
У неё есть $$$n$$$ подруг-бабушек (сама Марья Ивановна в это количество не входит). Бабушка с номером $$$i$$$ готова прийти на обряд при условии, если в момент её появления во дворе кроме неё там будет как минимум $$$a_i$$$ других бабушек. Обратите внимание, что бабушки могут приходить во двор одновременно. Формально, бабушка $$$i$$$ готова прийти, если количество бабушек пришедших ранее или одновременно с ней больше или равно $$$a_i$$$.
Бабушки собираются во дворе так.
Ваша задача — найти, какое максимальное количество бабушек (включая себя) Марья Ивановна может собрать во дворе для проведения обряда «обкуривания от Короны-Вируса». Ведь чем больше людей в одном месте во время карантина, тем эффективнее обряд!
Рассмотрим пример: если $$$n=6$$$ и $$$a=[1,5,4,5,1,9]$$$, то:
В первой строке находится одно целое число $$$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$$$-ю Марья Ивановна тоже не может. То есть во дворе будет только Марья Ивановна и три бабушки из первого шага.
Название |
---|