310339: CF1820C. Constructive Problem

C. Constructive Problemtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

As you know, any problem that does not require the use of complex data structures is considered constructive. You are offered to solve one of such problems.

You are given an array $a$ of $n$ non-negative integers. You are allowed to perform the following operation exactly once: choose some non-empty subsegment $a_l, a_{l+1}, \ldots, a_r$ of the array $a$ and a non-negative integer $k$, and assign value $k$ to all elements of the array on the chosen subsegment.

The task is to find out whether $\operatorname{MEX}(a)$ can be increased by exactly one by performing such an operation. In other words, if before the operation $\operatorname{MEX}(a) = m$ held, then after the operation it must hold that $\operatorname{MEX}(a) = m + 1$.

Recall that $\operatorname{MEX}$ of a set of integers $c_1, c_2, \ldots, c_k$ is defined as the smallest non-negative integer $x$ which does not occur in the set $c$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 50\,000$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 200\,000$) — the number of elements of array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — elements of array $a$.

It is guaranteed that the sum $n$ over all test cases does not exceed $200\,000$.

Output

For each test case, print "Yes" if you can increase $\operatorname{MEX}(a)$ by exactly one by performing the operation from the statement exactly once, otherwise print "No".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

ExampleInput

4
3
1 2 1
4
0 2 2 0
4
3 2 0 2
1
0

Output

Yes
Yes
No
No

Note

In the first test case, $\operatorname{MEX}(a) = 0$. If you set all elements of $a$ to $0$, then $\operatorname{MEX}$ of the resulting array will be $1$, and thus will increase by one.

In the second test case, $\operatorname{MEX}(a) = 1$. If we assign a value of $1$ to the elements of $a$ on a subsegment from $2$ to $3$, we get an array $[0, 1, 1, 0]$ for which $\operatorname{MEX}$ is $2$, and thus is increased by one compared to the original.

It can be shown that in the third and fourth test cases it is impossible to perform an operation so that the value of $\operatorname{MEX}(a)$ increases by exactly one.

题目大意：
这个问题是关于一个构造性问题。给定一个由非负整数组成的数组a，你可以执行一次以下操作：选择数组a的某个非空子段a_l, a_{l+1}, ..., a_r和一个非负整数k，并将值k赋给所选子段的所有元素。任务是找出是否可以通过执行这样的操作使得MEX(a)恰好增加一。回顾一下，一个整数集合c_1, c_2, ..., c_k的MEX定义为集合c中未出现的最小非负整数x。

输入数据格式：
每个测试包含多个测试用例。第一行包含测试用例的数量t（1 ≤ t ≤ 50,000）。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 200,000）——数组a的元素数量。
每个测试用例的第二行包含n个整数a_1, a_2, ..., a_n（0 ≤ a_i ≤ 10^9）——数组a的元素。
保证所有测试用例的n之和不超过200,000。

输出数据格式：
对于每个测试用例，如果你可以通过执行题目描述中的操作恰好一次来使MEX(a)增加一，则打印"Yes"，否则打印"No"。
输出答案时大小写不敏感，例如："yEs"、"yes"、"Yes"和"YES"都将被视为肯定回答。

示例：
输入：
4
3
1 2 1
4
0 2 2 0
4
3 2 0 2
1
0

输出：
Yes
Yes
No
No

注意：
在第一个测试用例中，MEX(a) = 0。如果将a的所有元素设置为0，则所得数组的MEX为1，因此增加了一。
在第二个测试用例中，MEX(a) = 1。如果我们将1赋值给a的从2到3的子段上的元素，我们得到一个数组[0, 1, 1, 0]，其MEX为2，因此比原始的MEX增加了一。
可以证明，在第三个和第四个测试用例中，不可能执行一个操作使得MEX(a)的值恰好增加一。题目大意： 这个问题是关于一个构造性问题。给定一个由非负整数组成的数组a，你可以执行一次以下操作：选择数组a的某个非空子段a_l, a_{l+1}, ..., a_r和一个非负整数k，并将值k赋给所选子段的所有元素。任务是找出是否可以通过执行这样的操作使得MEX(a)恰好增加一。回顾一下，一个整数集合c_1, c_2, ..., c_k的MEX定义为集合c中未出现的最小非负整数x。 输入数据格式： 每个测试包含多个测试用例。第一行包含测试用例的数量t（1 ≤ t ≤ 50,000）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 200,000）——数组a的元素数量。 每个测试用例的第二行包含n个整数a_1, a_2, ..., a_n（0 ≤ a_i ≤ 10^9）——数组a的元素。 保证所有测试用例的n之和不超过200,000。 输出数据格式： 对于每个测试用例，如果你可以通过执行题目描述中的操作恰好一次来使MEX(a)增加一，则打印"Yes"，否则打印"No"。 输出答案时大小写不敏感，例如："yEs"、"yes"、"Yes"和"YES"都将被视为肯定回答。 示例： 输入： 4 3 1 2 1 4 0 2 2 0 4 3 2 0 2 1 0 输出： Yes Yes No No 注意： 在第一个测试用例中，MEX(a) = 0。如果将a的所有元素设置为0，则所得数组的MEX为1，因此增加了一。 在第二个测试用例中，MEX(a) = 1。如果我们将1赋值给a的从2到3的子段上的元素，我们得到一个数组[0, 1, 1, 0]，其MEX为2，因此比原始的MEX增加了一。 可以证明，在第三个和第四个测试用例中，不可能执行一个操作使得MEX(a)的值恰好增加一。