题目描述

给定一个由 $n$ 个元素组成的整数数组 $a$，定义 $f(l, r) = \operatorname{MEX}([a_l, a_{l + 1}, \dots, a_r])$ $^{∗}$。

请判断是否可以对数组 $a$ 进行重排，使得对于每一个 $i$（$1 \le i \le n - 1$），都满足 $f(1, i) \neq f(i + 1, n)$。换句话说，对于每一个分割点 $i$，数组前缀的MEX值必须与后缀的MEX值不同。

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

输入格式

输入包含多组测试用例。第一行输入测试用例数 $t$（$1 \le t \le 500$），后续为各测试用例的描述。

每组测试用例的第一行输入一个整数 $n$（$2 \le n \le 100$），表示数组的长度。 第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le n$）。

输出格式

对于每组测试用例，若存在满足条件的重排方式，输出YES，否则输出 NO。 输出的大小写不做要求（例如 yEs、yes、Yes、YES 均视为正确答案）。

说明/提示

第一个样例中，数组的原始顺序就已经满足条件。此时唯一的分割点为 $i=1$，计算得 $f(1,1) = \operatorname{MEX}([1]) = 0$，$f(2,2) = \operatorname{MEX}([0]) = 1$。由于 $0 \neq 1$，条件成立。

第二个样例中，可以证明不存在满足条件的重排方式。例如考虑重排后的数组为 $[3, 0, 0]$，取分割点 $i=2$，则$f(1,2) = \operatorname{MEX}([3,0]) = 1$，$f(3,3) = \operatorname{MEX}([0]) = 1$，二者相等，因此该重排方式无效。

第三个样例中，可将数组重排为 $[1, 6, 1, 0, 0, 5]$。以分割点 $i=4$ 为例，$f(1,4) = \operatorname{MEX}([1,6,1,0]) = 2$，$f(5,6) = \operatorname{MEX}([0,5]) = 1$，满足条件。可以验证，该重排方式对所有分割点均满足条件。

样例

3
2
1 0
3
0 3 0
6
1 0 5 0 6 1

YES
NO
YES