给你一个大小为 $$$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]$$$,按非降序排序。
在第三、第四、第五和第六个测试用例中,可以证明数组不能按非降序排序。