B. Белая магия
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовём последовательность чисел $$$a_1, a_2, \ldots, a_n$$$ магической, если для всех $$$1 \leq i \leq n-1$$$ верно, что: $$$\operatorname{min}(a_1, \ldots, a_i) \geq \operatorname{mex}(a_{i+1}, \ldots, a_n)$$$. В частности, любая последовательность длины $$$1$$$ является магической.

Наименьшее исключенное (MEX) набора чисел $$$a_1, a_2, \ldots, a_k$$$ определяется как наименьшее неотрицательное целое число $$$t$$$, которое не встречается в наборе чисел $$$a$$$.

Вам дана последовательность $$$a$$$ из $$$n$$$ целых неотрицательных чисел. Найдите максимально возможную длину магической подпоследовательности$$$^{\text{∗}}$$$ последовательности $$$a$$$.

$$$^{\text{∗}}$$$Последовательность $$$a$$$ является подпоследовательностью $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.

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

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

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

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

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

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

Для каждого набора входных данных выведите одно число — максимально возможную длину магической подпоследовательности последовательности $$$a$$$.

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

В первом наборе входных данных сама последовательность $$$[4, 3, 2, 1, 0]$$$ является магической, так как:

  • $$$\operatorname{min}(4) = 4, \operatorname{mex}(3, 2, 1, 0) = 4$$$. $$$4 \geq 4$$$
  • $$$\operatorname{min}(4, 3) = 3, \operatorname{mex}(2, 1, 0) = 3$$$. $$$3 \geq 3$$$
  • $$$\operatorname{min}(4, 3, 2) = 2, \operatorname{mex}(1, 0) = 2$$$. $$$2 \geq 2$$$
  • $$$\operatorname{min}(4, 3, 2, 1) = 1, \operatorname{mex}(0) = 1$$$. $$$1 \geq 1$$$

Во втором наборе входных данных последовательность $$$[4, 3, 3, 2, 1, 0]$$$ не является магической, так как $$$\operatorname{min}(4, 3) = 3, \operatorname{mex}(3, 2, 1, 0) = 4$$$, $$$3 < 4$$$. Но подпоследовательность $$$[4, 3, 2, 1, 0]$$$ этой последовательности является магической, поэтому ответ $$$5$$$.