Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований.
Если вы раньше видели эти задачи,
виртуальное соревнование не для вас – решайте эти задачи в архиве.
Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве.
Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.
Алиса и Боб играют в игру. У них есть массив положительных целых чисел $$$a$$$ размера $$$n$$$.
Перед началом игры Алиса выбирает целое число $$$k \ge 0$$$. Игра длится $$$k$$$ ходов, номера ходов нумеруются от $$$1$$$ до $$$k$$$. На $$$i$$$-м ходу Алиса должна удалить из массива элемент, который меньше либо равен $$$k - i + 1$$$. После этого, если массив не пустой, Боб должен прибавить к некоторому элементу массива $$$k - i + 1$$$. Обратите внимание, что и действие Алисы, и следующее за ним действие Боба — это две части одного и того же хода. Если Алиса не может удалить элемент на каком-то ходу — она проигрывает. Если $$$k$$$-й ход закончился, а Алиса еще не проиграла, то она выигрывает.
Ваша задача — определить максимальное значение $$$k$$$, при котором Алиса может выиграть при оптимальной игре обоих игроков. Боб играет против Алисы, поэтому он пытается, если это возможно, заставить ее проиграть.
Входные данные
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — размер массива $$$a$$$.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное значение $$$k$$$, при котором Алиса может выиграть при оптимальной игре обоих игроков.