该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

如果对所有 $1 \leq i \leq n-1$ 都成立，我们称一个序列 $a _{1}, a _{2}, \ldots, a _{n}$为神奇序列：

$\operatorname{min}(a _{1}, \ldots, a _{i}) \geq \operatorname{mex}(a _{i+1}, \ldots, a _{n})$

.特别地，任何长度为 $1$ 的序列都被视为神奇序列

整数集合 {$a _{1}, a_{2}, \ldots, a_{k}$}的$mex$ 定义为在集合 $a$ 中不出现的最小非负整数 $t$

给你一个由 $n$ 个非负整数组成的序列 $a$ 。求序列 $a$的神奇子序列 $^{\text{∗}}$ 的最大可能长度。

$^{\text{∗}}$ 如果 $a$ 可以从 $b$ 中删除任意位置上的几个(可能是零个或全部)元素，则序列 $a$ 是序列 $b$ 的子序列

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 100$ )。测试用例说明如下。

每个测试用例的第一行都包含一个整数 $n$ ( $1 \leq n \leq 10^5$ ) - 序列 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a _{1}, a_{2}, \ldots, a_{n}$( $0 \leq a_{i} \leq 10^5$ ) --序列 $a$ 的元素。

输出格式

对于每个测试用例，输出一个数字 - 序列 $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$ 。