CF1819A.Constructive Problem

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$.

众所周知，任何不涉及复杂数据结构的问题均被视为构造性问题。本题即为其中一例。

给定一个长度为 $n$ 的非负整数数组 $a$。你被允许恰好执行一次如下操作：选择数组 $a$ 的某个非空子段 $a_l, a_{l+1}, \ldots, a_r$ 和一个非负整数 $k$，并将该子段内所有元素的值均赋为 $k$。

你的任务是判断：能否通过执行上述操作，使得数组 $a$ 的 $\operatorname{MEX}(a)$ 恰好增加 1？换言之，若操作前 $\operatorname{MEX}(a) = m$，则操作后必须满足 $\operatorname{MEX}(a) = m + 1$。

需要回顾的是：集合 $c_1, c_2, \ldots, c_k$ 的 $\operatorname{MEX}$ 定义为未出现在该集合中的最小非负整数 $x$。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

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.

对于每个测试用例，如果可以通过恰好执行一次题目所述的操作，使得 $\operatorname{MEX}(a)$ 恰好增加 $1$，则输出“Yes”；否则输出“No”。

你可以以任意大小写形式输出答案（大写或小写均可）。例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 均会被识别为肯定回答。

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.

在第一个测试用例中，$\operatorname{MEX}(a) = 0$。若将数组 $a$ 的所有元素均设为 $0$，则所得数组的 $\operatorname{MEX}$ 为 $1$，因此恰好增加 $1$。

在第二个测试用例中，$\operatorname{MEX}(a) = 1$。若将数组 $a$ 中从位置 $2$ 到位置 $3$ 的子段内所有元素赋值为 $1$，则得到数组 $[0, 1, 1, 0]$，其 $\operatorname{MEX}$ 为 $2$，相比原数组恰好增加 $1$。

可以证明，在第三和第四个测试用例中，无法执行任何操作使得 $\operatorname{MEX}(a)$ 的值恰好增加 $1$。