F. Падшие башни
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пизано построил массив $$$a$$$ из $$$n$$$ башен, каждая из которых состоит из $$$a_i \ge 0$$$ кубиков.

Пизано может уронить башню так, что $$$a_i$$$ следующих башен вырастут на $$$1$$$. Иными словами, он может взять элемент $$$a_i$$$, увеличить на единицу следующие $$$a_i$$$ элементов, а затем приравнять $$$a_i$$$ к $$$0$$$. При этом кубики, которые упали за границу массива башен, исчезают. Если Пизано роняет башню из $$$0$$$ кубиков, ничего не происходит.

Пизано хочет уронить все $$$n$$$ башен в любом порядке, каждую ровно по одному разу. То есть для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ он уронит башню на позиции $$$i$$$ ровно один раз.

Кроме того, в итоге массив высот башен должен стать неубывающим. То есть после того, как он уронит все $$$n$$$ башен, для любых $$$i \lt j$$$ башня на позиции $$$i$$$ должна быть не выше, чем башня на позиции $$$j$$$.

Требуется вывести максимальный $$$\text{MEX}$$$ массива высот башен, который можно получить в итоге.

$$$\text{MEX}$$$ массива — это минимальное неотрицательное целое число, которое не представлено в массиве.

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

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

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — количество башен.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел — изначальные высоты башен $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$).

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

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

Для каждого набора входных данных выведите одно целое число — максимальный $$$\text{MEX}$$$ итогового массива.

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

Пояснение к первому набору входных данных.

Пояснение ко второму набору входных данных. Обратите внимание, что все башни были обрушены ровно по одному разу, а итоговый массив высот неубывающий.