← 返回题目列表

Codeforces · 1750/A

A. 间接排序

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

给你一个大小为 $$$n$$$ 的排列 $$$a_1, a_2, \ldots, a_n$$$,其中从 $$$1$$$ 到 $$$n$$$ 的每个整数只出现一次。

您可以执行以下操作任意次数(可能为零):

- 选择任意三个索引 $$$i, j, k$$$ ($$$1 \le i < j < k \le n$$$)。
- 如果 $$$a_i > a_k$$$,则将 $$$a_i$$$ 替换为 $$$a_i + a_j$$$。否则,交换 $$$a_j$$$ 和 $$$a_k$$$。

确定是否可以使数组 $$$a$$$ 按非降序排序。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 10$$$) — 数组 $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\dots,a_n$$$ ($$$1 \le a_i \le n$$$, $$$a_i \neq a_j$$$ if $$$i \neq j$$$) — 数组 $$$a$$$ 的元素。

输出

对于每个测试用例,如果数组可以按非降序排序,则输出“Yes”(不带引号),否则输出“No”(不带引号)。

在任何情况下都可以输出“Yes”和“No”(例如,字符串“YES”、“yEs”和“yes”将被识别为肯定响应)。

示例

输入 #1

7
3
1 2 3
3
1 3 2
7
5 3 4 7 6 2 1
7
7 6 5 4 3 2 1
5
2 1 4 5 3
5
2 1 3 4 5
7
1 2 6 7 4 3 5

输出 #1

Yes
Yes
No
No
No
No
Yes

注意

在第一个测试用例中,$$$[1,2,3]$$$ 已按非降序排序。

在第二个测试用例中,我们可以选择$$$i = 1,j = 2,k = 3$$$。由于 $$$a_1 \le a_3$$$,交换 $$$a_2$$$ 和 $$$a_3$$$,则数组变为 $$$[1,2,3]$$$,按非降序排序。

在第七个测试用例中,我们可以依次进行以下操作:

- 选择 $$$i = 5,j = 6,k = 7$$$。由于$$$a_5 \le a_7$$$,交换$$$a_6$$$和$$$a_7$$$,数组就变成$$$[1,2,6,7,4,5,3]$$$。
- 选择 $$$i = 5,j = 6,k = 7$$$。由于 $$$a_5 > a_7$$$,将 $$$a_5$$$ 替换为 $$$a_5+a_6=9$$$,则数组变为 $$$[1,2,6,7,9,5,3]$$$。
- 选择 $$$i = 2,j = 5,k = 7$$$。由于$$$a_2 \le a_7$$$,交换$$$a_5$$$和$$$a_7$$$,数组就变成$$$[1,2,6,7,3,5,9]$$$。
- 选择 $$$i = 2,j = 4,k = 6$$$。由于$$$a_2 \le a_6$$$,交换$$$a_4$$$和$$$a_6$$$,数组就变成$$$[1,2,6,5,3,7,9]$$$。
- 选择 $$$i = 1,j = 3,k = 5$$$。由于 $$$a_1 \le a_5$$$,交换 $$$a_3$$$ 和 $$$a_5$$$,则数组变为 $$$[1,2,3,5,6,7,9]$$$,按非降序排序。

在第三、第四、第五和第六个测试用例中,可以证明数组不能按非降序排序。