← 返回题目列表

Codeforces · 1670/A

A. 斯利姆教授

中文机器翻译题面 查看原题

有一天,斯利姆教授决定离开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 元素的符号交换,这样数组就会排序。

在第四个测试用例中,无法使用该操作对数组进行任意次数的排序。