← 返回题目列表

Codeforces · 2191/B

B. MEX 重新排序

中文机器翻译题面 查看原题

给定一个由 $$$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) 被定义为集合 $$$c$$$ 中不出现的最小非负整数 $$$x$$$。

输入

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

输出

输出“是" 如果您可以重新排序 $$$a$$$ 以满足语句中的条件,并且 "NO”否则。您可以在任何情况下输出答案(上限或下限)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

示例

输入
复制

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

输出
复制

YES
NO
YES

注意

在第一个示例中,$$$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$$$也满足该条件。