有一天,斯利姆教授决定离开GUC王国,加入GIU王国。在加入 GIU 之前,他接受了一项简单的在线评估。 GUC的公民看到教授离开感到高兴和悲伤,因此他们决定侵入系统并将在线评估改为更难的评估,以便他留在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$$$。
Slim教授看到这个问题还是太简单了,不值得他花时间,所以他决定把它交给你来解决。
输入
第一行包含一个整数 $$$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”。您可以以任何大小写(大写或小写)打印每个字母。
示例
输入 #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
输出 #1
NO YES YES NO
注意
在第一个测试用例中,无法使用该操作对数组进行任意多次排序。
在第二个测试用例中,数组已经排序。
在第三个测试用例中,我们可以将 $$$1$$$-st 元素的符号与第 $$$5$$$ 个元素的符号交换,并将 $$$3$$$-rd 元素的符号与第 $$$6$$$-th 元素的符号交换,这样数组就会排序。
在第四个测试用例中,无法使用该操作对数组进行任意次数的排序。