Indirect Sort

题意翻译

给定 $T$ 组数据，每组数据给定 $n$ 以及长度为 $n$ 的排列 $a$，可以进行若干次操作，每次操作可以选择三个数 $i,j,k \ (1 \le i < j < k \le n)$，若 $a_i > a_k$ 将 $a_i$ 加上 $a_j$，否则交换 $a_j,a_k$，问是否能使排列单调递增。 by Shan_Creeper.

题目描述

You are given a permutation $ a_1, a_2, \ldots, a_n $ of size $ n $ , where each integer from $ 1 $ to $ n $ appears exactly once. You can do the following operation any number of times (possibly, zero): - Choose any three indices $ i, j, k $ ( $ 1 \le i < j < k \le n $ ). - If $ a_i > a_k $ , replace $ a_i $ with $ a_i + a_j $ . Otherwise, swap $ a_j $ and $ a_k $ . Determine whether you can make the array $ a $ sorted in non-descending order.

输入输出格式

输入格式

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 5000 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains a single integer $ n $ ( $ 3 \le n \le 10 $ ) — the length of the array $ a $ . The second line contains $ n $ integers $ a_1,a_2,\dots,a_n $ ( $ 1 \le a_i \le n $ , $ a_i \neq a_j $ if $ i \neq j $ ) — the elements of the array $ a $ .

输出格式

For each test case, output "Yes" (without quotes) if the array can be sorted in non-descending order, and "No" (without quotes) otherwise. You can output "Yes" and "No" in any case (for example, strings "YES", "yEs" and "yes" will be recognized as a positive response).

输入输出样例

输入样例 #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

说明

In the first test case, $ [1,2,3] $ is already sorted in non-descending order. In the second test case, we can choose $ i = 1,j = 2,k = 3 $ . Since $ a_1 \le a_3 $ , swap $ a_2 $ and $ a_3 $ , the array then becomes $ [1,2,3] $ , which is sorted in non-descending order. In the seventh test case, we can do the following operations successively: - Choose $ i = 5,j = 6,k = 7 $ . Since $ a_5 \le a_7 $ , swap $ a_6 $ and $ a_7 $ , the array then becomes $ [1,2,6,7,4,5,3] $ . - Choose $ i = 5,j = 6,k = 7 $ . Since $ a_5 > a_7 $ , replace $ a_5 $ with $ a_5+a_6=9 $ , the array then becomes $ [1,2,6,7,9,5,3] $ . - Choose $ i = 2,j = 5,k = 7 $ . Since $ a_2 \le a_7 $ , swap $ a_5 $ and $ a_7 $ , the array then becomes $ [1,2,6,7,3,5,9] $ . - Choose $ i = 2,j = 4,k = 6 $ . Since $ a_2 \le a_6 $ , swap $ a_4 $ and $ a_6 $ , the array then becomes $ [1,2,6,5,3,7,9] $ . - Choose $ i = 1,j = 3,k = 5 $ . Since $ a_1 \le a_5 $ , swap $ a_3 $ and $ a_5 $ , the array then becomes $ [1,2,3,5,6,7,9] $ , which is sorted in non-descending order. In the third, the fourth, the fifth and the sixth test cases, it can be shown that the array cannot be sorted in non-descending order.

**间接排序**

**题意翻译：**
给定 $ T $ 组数据，每组数据给定 $ n $ 以及长度为 $ n $ 的排列 $ a $，可以进行若干次操作，每次操作可以选择三个数 $ i,j,k \ (1 \le i < j < k \le n) $，若 $ a_i > a_k $ 将 $ a_i $ 加上 $ a_j $，否则交换 $ a_j,a_k $，问是否能使排列单调递增。

**题目描述：**
给定一个大小为 $ 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 $ 如果 $ 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**间接排序** **题意翻译：** 给定 $ T $ 组数据，每组数据给定 $ n $ 以及长度为 $ n $ 的排列 $ a $，可以进行若干次操作，每次操作可以选择三个数 $ i,j,k \ (1 \le i < j < k \le n) $，若 $ a_i > a_k $ 将 $ a_i $ 加上 $ a_j $，否则交换 $ a_j,a_k $，问是否能使排列单调递增。 **题目描述：** 给定一个大小为 $ 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 $ 如果 $ 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