B. White Magic

题目描述

我们称一个序列 $a_1,a_2,\dots,a_n$ 为魔法序列，当且仅当对于所有的 $1 \le i \le n-1$ 都满足：

$$\min(a_1,\dots,a_i) \ge \operatorname{mex}(a_{i+1},\dots,a_n) $$

特别地，任意长度为 $1$ 的序列都是魔法序列。

一个整数集合 $a_1,a_2,\dots,a_k$ 的**最小未出现整数（MEX）**定义为：不存在于集合 $a$ 中的最小非负整数 $t$。

给定一个长度为 $n$ 的非负整数序列 $a$。请你求出序列 $a$ 的魔法子序列的最大可能长度。

补充定义：如果序列 $a$ 可以通过从序列 $b$ 中删除任意位置的若干个元素（可以删除 $0$ 个或全部）得到，那么 $a$ 是 $b$ 的子序列。

---

输入格式

每个测试点包含多组测试数据。 第一行输入测试数据组数 $t$（$1 \le t \le 10^4$）。

每组测试数据格式如下： 第一行输入一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示序列 $a$ 的长度。 第二行输入 $n$ 个非负整数 $a_1,a_2,\dots,a_n$（$0 \le a_i \le 10^9$）。

保证所有测试数据的 $n$ 之和不超过 $2 \cdot 10^5$。

---

输出格式

对于每组测试数据，输出一个整数，表示答案。

---

样例输入

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]$ 是魔法序列，验证如下：

• $\min(4)=4$，$\operatorname{mex}(3,2,1,0)=4$，满足 $4 \ge 4$
• $\min(4,3)=3$，$\operatorname{mex}(2,1,0)=3$，满足 $3 \ge 3$
• $\min(4,3,2)=2$，$\operatorname{mex}(1,0)=2$，满足 $2 \ge 2$
• $\min(4,3,2,1)=1$，$\operatorname{mex}(0)=1$，满足 $1 \ge 1$

在第二组测试用例中，原序列 $[4,3,3,2,1,0]$ 不是魔法序列，但它的子序列 $[4,3,2,1,0]$ 是魔法序列，因此答案为 $5$。