如果对于所有 $$$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$$$。