CF2191B.MEX Reordering

You are given an integer array $a$ consisting of $n$ elements. Denote $f(l, r) = \operatorname{MEX}([a_l, a_{l + 1}, \ldots, a_r])$$^{\text{∗}}$.

Determine if there is a way to reorder the array $a$ such that for every $i$ ($1 \le i \le n - 1$), $f(1, i) \neq f(i + 1, n)$. In other words, for every split point $i$, the $\operatorname{MEX}$ of the prefix must be different from the $\operatorname{MEX}$ of the suffix.

$^{\text{∗}}$The minimum excluded (MEX) of a collection of integers $c_1, c_2, \ldots, c_k$ is defined as the smallest non-negative integer $x$ which does not occur in the collection $c$.

给你一个包含 $n$ 个元素的整数数组 $a$。记 $f(l, r) = \operatorname{MEX}([a_l, a_{l + 1}, \ldots, a_r])$$^{\text{∗}}$。

判断是否存在一种对数组 $a$ 的重排方式，使得对每个 $i$（$1 \le i \le n - 1$），均有 $f(1, i) \neq f(i + 1, n)$。换言之，对每个分割点 $i$，前缀的 $\operatorname{MEX}$ 必须不等于后缀的 $\operatorname{MEX}$。

$^{\text{∗}}$ 一个整数集合 $c_1, c_2, \ldots, c_k$ 的**最小未出现值（MEX）**定义为不在该集合中出现的最小非负整数 $x$。

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

The first line of each test case contains a single integer $n$ ($2 \le n \le 100$) — the length of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le n$).

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 500$）。随后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 100$）—— 数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le n$）。

Output "YES" if you can reorder $a$ so that the condition from the statement is satisfied, and "NO" otherwise. 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.

如果可以对 $a$ 进行重排，使得题目陈述中的条件得到满足，则输出 "YES"；否则输出 "NO"。答案的大小写不限（即不区分大小写）。例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 均被视为肯定回答。

In the first example, the initial ordering of $a$ already satisfies the condition. The only choice for $i$ is $i = 1$. Then $f(1, i) = f(1, 1) = \operatorname{MEX}([a_1]) = \operatorname{MEX}([1]) = 0$, and $f(i + 1, n) = f(2, 2) = \operatorname{MEX}([a_2]) = \operatorname{MEX}([0]) = 1$. Since $0 \neq 1$, the condition is satisfied.

In the second example, it can be shown that there is no way to reorder $a$ to satisfy the condition. As an example, consider the order $a = [3, 0, 0]$ and $i = 2$. We have $f(1, i) = f(1, 2) = \operatorname{MEX}([a_1, a_2]) = \operatorname{MEX}([3, 0]) = 1$, and $f(i + 1, n) = f(3, 3) = \operatorname{MEX}([a_3]) = \operatorname{MEX}([0]) = 1$, hence $f(1, i) = f(i + 1, n)$, so the choice of reordering is invalid.

In the third example, we can reorder $a$ into $[1, 6, 1, 0, 0, 5]$. When $i = 4$, $f(1, i) = f(1, 4) = \operatorname{MEX}([a_1, a_2, a_3, a_4]) = \operatorname{MEX}([1, 6, 1, 0]) = 2$, $f(i + 1, n) = f(5, 6) = \operatorname{MEX}([a_5, a_6]) = \operatorname{MEX}([0, 5]) = 1$, so the condition is satisfied for this $i$. It can be verified that the condition is also satisfied for all other $i$.

在第一个例子中，数组 $a$ 的初始排列已满足条件。此时唯一可选的 $i$ 是 $i = 1$。于是 $f(1, i) = f(1, 1) = \operatorname{MEX}([a_1]) = \operatorname{MEX}([1]) = 0$，而 $f(i + 1, n) = f(2, 2) = \operatorname{MEX}([a_2]) = \operatorname{MEX}([0]) = 1$。由于 $0 \neq 1$，条件成立。

在第二个例子中，可以证明不存在对 $a$ 的重排方式使其满足条件。例如，考虑排列 $a = [3, 0, 0]$ 并取 $i = 2$：此时 $f(1, i) = f(1, 2) = \operatorname{MEX}([a_1, a_2]) = \operatorname{MEX}([3, 0]) = 1$，且 $f(i + 1, n) = f(3, 3) = \operatorname{MEX}([a_3]) = \operatorname{MEX}([0]) = 1$，因此 $f(1, i) = f(i + 1, n)$，该重排方案不合法。

在第三个例子中，可将 $a$ 重排为 $[1, 6, 1, 0, 0, 5]$。当 $i = 4$ 时，有 $f(1, i) = f(1, 4) = \operatorname{MEX}([a_1, a_2, a_3, a_4]) = \operatorname{MEX}([1, 6, 1, 0]) = 2$，而 $f(i + 1, n) = f(5, 6) = \operatorname{MEX}([a_5, a_6]) = \operatorname{MEX}([0, 5]) = 1$，故该 $i$ 满足条件。可以验证，该重排对所有其他 $i$ 值也均满足条件。