Однажды профессор Слим решил покинуть королевство GUC и переехать в королевство GIU. Чтобы быть принятым в GIU, он должен сначала пройти несложный онлайн-тест. Жители GUC были счастливы расстроены, что профессор уезжает, поэтому они решили взломать систему и поменять задачу в тесте на более сложную. После долгих обсуждений они сошлись на следующей задаче.
Дан массив из \(n\) целых чисел \(a_1,a_2,\ldots,a_n\), где \(a_{i} \neq 0\), проверьте, можно ли сделать этот массив отсортированным, применив следующую операцию несколько (возможно, ноль) раз. Массив называется отсортированным, если его элементы расположены в порядке неубывания.
- выберете два индекса \(i\) и \(j\) (\(1 \le i,j \le n\)) такие, что числа \(a_i\) и \(a_j\) различного знака. Другими словами, одно из этих чисел должно быть положительно, а другое отрицательно.
- поменяйте местами знаки чисел \(a_{i}\) и \(a_{j}\). Например, если \(a_i=3\), а \(a_j=-2\), то они изменятся на \(a_i=-3\) и \(a_j=2\).
Профессор Слим понял, что задача все еще простая и не стоит его времени, поэтому он предоставил вам возможность решить ее.
Выходные данные
Для каждого набора входных данных выведите «YES», если массив может быть отсортирован в порядке неубывания, иначе выведите «NO». Можно выводить каждую букву в любом регистре (верхнем или нижнем).
Примечание
В первом наборе нет способа сделать массив отсортированным.
Во втором наборе массив уже отсортирован.
В третьем наборе можно поменять знаки \(1\)-го и \(5\)-го элементов, а затем знаки \(3\)-го и \(6\)-го элементов, после чего массив будет отсортирован.
В четвертом примере нет способа сделать массив отсортированным.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|