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

Вам дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$. Вам разрешено выполнять следующую операцию любое число раз (возможно, ноль):

  • Выберите индекс $$$i$$$ ($$$1\le i\le n$$$). Умножьте $$$a_i$$$ на $$$-1$$$ (т.е. присвойте $$$a_i := -a_i$$$).

Ваша задача — определить, возможно ли сделать элемент с индексом $$$1$$$ медианой массива после выполнения вышеуказанной операции любое количество раз. Обратите внимание, что операции могут применяться и к индексу $$$1$$$, что означает, что медианой может оказаться как оригинальное значение $$$a_1$$$, так и его отрицание.

Медиана массива $$$b_1, b_2, \ldots, b_m$$$ определяется как $$$\left\lceil \frac{m}{2} \right\rceil$$$-й$$$^{\text{∗}}$$$ по величине элемент массива $$$b$$$. Например, медиана массива $$$[3, 1, 2]$$$ равна $$$2$$$, а медиана массива $$$[10, 1, 8, 3]$$$ равна $$$3$$$.

Гарантируется, что абсолютные значения элементов массива $$$a$$$ различны. Формально, нет пар индексов $$$1\le i \lt j\le n$$$, для которых $$$|a_i| = |a_j|$$$.

$$$^{\text{∗}}$$$$$$\lceil x \rceil$$$ — это функция округления вверх, которая возвращает наименьшее целое число, большее или равное $$$x$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 10^5$$$) — длина массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$|a_i|\le 10^6$$$, $$$|a_i|\neq |a_j|$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

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

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

Пример
Входные данные
7
3
2 3 1
5
1 2 3 4 5
4
4 2 0 -5
4
-5 0 4 3
4
-10 8 3 2
1
1
10
9 1000 -999 -13 456 -223 23 24 10 0
Выходные данные
YES
YES
YES
NO
NO
YES
YES
Примечание

В первом наборе входных данных $$$a_1 = 2$$$ уже является медианой массива $$$a = [2, 3, 1]$$$, поэтому операции не требуются.

Во втором наборе входных данных мы можем выполнить две операции: одну на индексе $$$2$$$ и одну на индексе $$$5$$$. Массив становится $$$[1, -2, 3, 4, -5]$$$, и его медиана равна $$$1$$$.

В третьем наборе входных данных, если вы выполните операцию на индексе $$$1$$$, массив станет $$$[-4, 2, 0, -5]$$$, и его медиана равна $$$-4$$$.

В четвертом наборе входных данных можно доказать, что никакая последовательность операций не может сделать медиану массива равной $$$5$$$ или $$$-5$$$.