如您所知,任何不需要使用复杂数据结构的问题都被认为是建设性的。您被要求解决此类问题之一。
给定一个由 $$$n$$$ 个非负整数组成的数组 $$$a$$$。您可以只执行一次以下操作:选择数组 $$$a$$$ 的一些非空子段 $$$a_l, a_{l+1}, \ldots, a_r$$$ 和一个非负整数 $$$k$$$,并将值 $$$k$$$ 分配给所选子段上数组的所有元素。
任务是找出 $$$\operatorname{MEX}(a)$$$ 是否可以通过执行这样的操作恰好增加 1。换句话说,如果在运算之前$$$\operatorname{MEX}(a) = m$$$成立,那么在运算之后它必须成立$$$\operatorname{MEX}(a) = m + 1$$$。
回想一下,整数集合 $$$c_1, c_2, \ldots, c_k$$$ 的 $$$\operatorname{MEX}$$$ 被定义为集合 $$$c$$$ 中不出现的最小非负整数 $$$x$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 50\,000$$$) - 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 200\,000$$$) — 数组 $$$a$$$ 的元素数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的总和 $$$n$$$ 不超过 $$$200\,000$$$。
输出
对于每个测试用例,如果可以通过执行语句中的操作一次将 $$$\operatorname{MEX}(a)$$$ 恰好增加 1,则打印“Yes”,否则打印“No”。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。
示例
输入 #1
4 3 1 2 1 4 0 2 2 0 4 3 2 0 2 1 0
输出 #1
Yes Yes No No
注意
在第一个测试用例中,$$$\operatorname{MEX}(a) = 0$$$。如果将 $$$a$$$ 的所有元素设置为 $$$0$$$,则结果数组的 $$$\operatorname{MEX}$$$ 将为 $$$1$$$,因此将增加 1。
在第二个测试用例中,$$$\operatorname{MEX}(a) = 1$$$。如果我们将 $$$1$$$ 的值赋给从 $$$2$$$ 到 $$$3$$$ 的子段上的 $$$a$$$ 的元素,我们将得到一个数组 $$$[0, 1, 1, 0]$$$,其中 $$$\operatorname{MEX}$$$ 为 $$$2$$$,因此与原始数组相比增加了 1。
可以看出,在第三和第四个测试用例中,不可能执行使 $$$\operatorname{MEX}(a)$$$ 的值恰好增加 1 的操作。