← 返回题目列表

Codeforces · 2066/B

B. 白魔法

中文机器翻译题面 查看原题

如果对于所有 $$$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{*}}$$$的最大可能长度。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 的神奇子序列的最大可能长度。

示例

输入 #1

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

输出 #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$$$。