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

Однажды профессор Слим решил покинуть королевство GUC и переехать в королевство GIU. Чтобы быть принятым в GIU, он должен сначала пройти несложный онлайн-тест. Жители GUC были счастливы расстроены, что профессор уезжает, поэтому они решили взломать систему и поменять задачу в тесте на более сложную. После долгих обсуждений они сошлись на следующей задаче.

Дан массив из $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$, где $$$a_{i} \neq 0$$$, проверьте, можно ли сделать этот массив отсортированным, применив следующую операцию несколько (возможно, ноль) раз. Массив называется отсортированным, если его элементы расположены в порядке неубывания.

  1. выберете два индекса $$$i$$$ и $$$j$$$ ($$$1 \le i,j \le n$$$) такие, что числа $$$a_i$$$ и $$$a_j$$$ различного знака. Другими словами, одно из этих чисел должно быть положительно, а другое отрицательно.
  2. поменяйте местами знаки чисел $$$a_{i}$$$ и $$$a_{j}$$$. Например, если $$$a_i=3$$$, а $$$a_j=-2$$$, то они изменятся на $$$a_i=-3$$$ и $$$a_j=2$$$.

Профессор Слим понял, что задача все еще простая и не стоит его времени, поэтому он предоставил вам возможность решить ее.

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

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

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

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_{i} \le 10^9$$$, $$$a_{i} \neq 0$$$) — массив $$$a$$$.

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

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

Для каждого набора входных данных выведите «YES», если массив может быть отсортирован в порядке неубывания, иначе выведите «NO». Можно выводить каждую букву в любом регистре (верхнем или нижнем).

Пример
Входные данные
4
7
7 3 2 -11 -13 -17 -23
6
4 10 25 47 71 96
6
71 -35 7 -4 -11 -25
6
-45 9 -48 -67 -55 7
Выходные данные
NO
YES
YES
NO
Примечание

В первом наборе нет способа сделать массив отсортированным.

Во втором наборе массив уже отсортирован.

В третьем наборе можно поменять знаки $$$1$$$-го и $$$5$$$-го элементов, а затем знаки $$$3$$$-го и $$$6$$$-го элементов, после чего массив будет отсортирован.

В четвертом примере нет способа сделать массив отсортированным.