B. Перестановка MEX
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив целых чисел $$$a$$$, состоящий из $$$n$$$ элементов. Обозначим $$$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{∗}}$$$Наименьшее исключенное (MEX) набора чисел $$$c_1, c_2, \ldots, c_k$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе чисел $$$c$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$).

Выходные данные

Выведите «YES» если вы можете переставить $$$a$$$ так, чтобы условие из задачи было выполнено, и «NO» в противном случае. Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
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$$$.