Алиса и Боб играют в игру. У них есть массив положительных целых чисел $$$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$$$, при котором Алиса может выиграть при оптимальной игре обоих игроков.
431 1 244 4 4 41151 3 2 1 1
2 0 1 3
Название |
---|