CF2066B White Magic

我们称一个序列 $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$ 的序列都被视为魔法序列。 一个整数集合 $a_1, a_2, \ldots, a_k$ 的最小未出现值（MEX）被定义为未出现在该集合中的最小非负整数 $t$。 给定一个由 $n$ 个非负整数构成的序列 $a$。请找到该序列的魔法子序列$^{\text{∗}}$ 的最大可能长度。 $^{\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$ 的魔法子序列的最大可能长度。

在第一个测试用例中，序列 $[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$。 翻译由 DeepSeek R1 完成