A. Микс-Mex-Макс
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$, состоящий из $$$n$$$ целых неотрицательных чисел. Однако некоторые элементы массива $$$a$$$ отсутствуют, и они представлены значением $$$−1$$$.

Назовём массив $$$a$$$ хорошим, если и только если для каждого $$$1 \leq i \leq n-2$$$ выполняется следующее:

$$$$$$ \operatorname{mex}([a_i, a_{i+1}, a_{i+2}]) = \max([a_i, a_{i+1}, a_{i+2}]) - \min([a_i, a_{i+1}, a_{i+2}]), $$$$$$

где $$$\operatorname{mex}(b)$$$ обозначает минимальное исключенное значение (MEX)$$$^{\text{∗}}$$$ целых чисел в $$$b$$$.

Вам необходимо определить, можно ли сделать массив $$$a$$$ хорошим после замены каждого $$$-1$$$ в массиве $$$a$$$ на целое неотрицательное число.

$$$^{\text{∗}}$$$Наименьшее исключенное (MEX) набора чисел $$$b_1, b_2, \ldots, b_k$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе чисел $$$b$$$. Например, $$$\operatorname{mex}([2,2,1])=0$$$, потому что $$$0$$$ не принадлежит массиву, а $$$\operatorname{mex}([0,3,1,2])=4$$$, потому что $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$ присутствуют в массиве, а $$$4$$$ — нет.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \leq n \leq 100$$$) — длину массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$-1 \leq a_i \leq 100$$$) — элементы массива $$$a$$$. $$$a_i = -1$$$ обозначает, что этот элемент отсутствует.

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

Для каждого набора входных данных выведите «YES», если возможно сделать массив $$$a$$$ хорошим, и «NO» в противном случае.

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

Пример
Входные данные
8
3
-1 -1 -1
5
1 1 1 1 0
6
5 5 1 -1 -1 1
4
-1 -1 0 -1
4
-1 1 1 -1
3
3 3 -1
5
0 0 0 0 0
7
3 0 1 4 -1 2 3
Выходные данные
YES
NO
NO
NO
YES
YES
NO
NO
Примечание

В первом наборе входных данных сделаем $$$ a_1 = a_2 = a_3 = 1 $$$. Тогда

  • $$$\operatorname{mex}([a_1, a_2, a_3]) = \operatorname{mex}([1, 1, 1]) = 0$$$;
  • $$$\max([a_1, a_2, a_3]) = \max([1, 1, 1]) = 1$$$;
  • $$$\min([a_1, a_2, a_3]) = \min([1, 1, 1]) = 1$$$.

И $$$0 = 1 - 1$$$. Поэтому массив $$$a$$$ стал хорошим.

Во втором наборе ни один из элементов массива $$$a$$$ не отсутствует. В данном случае

  • $$$\operatorname{mex}([a_1, a_2, a_3]) = \max([a_1, a_2, a_3]) - \min([a_1, a_2, a_3])$$$,
  • $$$\operatorname{mex}([a_2, a_3, a_4]) = \max([a_2, a_3, a_4]) - \min([a_2, a_3, a_4])$$$, но
  • $$$\operatorname{mex}([a_3, a_4, a_5]) \ne \max([a_3, a_4, a_5]) - \min([a_3, a_4, a_5])$$$.

Поэтому массив $$$a$$$ не может стать хорошим.

Во третьем наборе входных данных ни один из $$$a_1$$$, $$$a_2$$$ или $$$a_3$$$ не отсутствует. Однако,

  • $$$\operatorname{mex}([a_1, a_2, a_3]) = \operatorname{mex}([5, 5, 1]) = 0$$$;
  • $$$\max([a_1, a_2, a_3]) = \max([5, 5, 1]) = 5$$$;
  • $$$\min([a_1, a_2, a_3]) = \min([5, 5, 1]) = 1$$$.

И $$$0\ne 5 - 1$$$. Таким образом, массив $$$a$$$ не может стать хорошим, независимо от того, как вы замените отсутствующие элементы.