310832: CF1896A. Jagged Swaps

A. Jagged Swapstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a permutation$^\dagger$ $a$ of size $n$. You can do the following operation

• Select an index $i$ from $2$ to $n - 1$ such that $a_{i - 1} < a_i$ and $a_i > a_{i+1}$. Swap $a_i$ and $a_{i+1}$.

Determine whether it is possible to sort the permutation after a finite number of operations.

$^\dagger$ A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5000$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($3 \le n \le 10$) — the size of the permutation.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the elements of permutation $a$.

Output

For each test case, print "YES" if it is possible to sort the permutation, and "NO" otherwise.

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

ExampleInput

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

Output

YES
YES
NO
NO
NO
NO

Note

In the first test case, the permutation is already sorted.

In the second test case, we can choose index $i=2$ as $1<3$ and $3>2$ to form $[1, 2, 3, 5, 4]$. Then, we can choose index $i=4$ as $3<5$ and $5>4$ to form $[1, 2, 3, 4, 5]$.

In the third test case, it can be proven that it is impossible to sort the permutation.

题目大意：
给定一个大小为n的排列a。你可以进行以下操作：
- 从2到n-1中选择一个索引i，使得a_{i-1} < a_i且a_i > a_{i+1}。交换a_i和a_{i+1}。
确定是否可以通过有限次操作对排列进行排序。

输入数据格式：
每个测试包含多个测试用例。第一行包含测试用例数t（1≤t≤5000）。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（3≤n≤10）——排列的大小。
每个测试用例的第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤n）——排列a的元素。

输出数据格式：
对于每个测试用例，如果可以排序排列，则打印"YES"，否则打印"NO"。
你可以以任何大小写打印每个字母（例如，"YES"、"Yes"、"yes"、"yEs"都将被视为肯定答案）。

示例：
输入：
6
3
1 2 3
5
1 3 2 5 4
5
5 4 3 2 1
3
3 1 2
4
2 3 1 4
5
5 1 2 3 4
输出：
YES
YES
NO
NO
NO
NO

注意：
在第一个测试用例中，排列已经排序。
在第二个测试用例中，我们可以选择索引i=2，因为1<3且3>2，得到[1, 2, 3, 5, 4]。然后，我们可以选择索引i=4，因为3<5且5>4，得到[1, 2, 3, 4, 5]。
在第三个测试用例中，可以证明无法对排列进行排序。题目大意： 给定一个大小为n的排列a。你可以进行以下操作： - 从2到n-1中选择一个索引i，使得a_{i-1} < a_i且a_i > a_{i+1}。交换a_i和a_{i+1}。 确定是否可以通过有限次操作对排列进行排序。 输入数据格式： 每个测试包含多个测试用例。第一行包含测试用例数t（1≤t≤5000）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（3≤n≤10）——排列的大小。 每个测试用例的第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤n）——排列a的元素。 输出数据格式： 对于每个测试用例，如果可以排序排列，则打印"YES"，否则打印"NO"。 你可以以任何大小写打印每个字母（例如，"YES"、"Yes"、"yes"、"yEs"都将被视为肯定答案）。 示例： 输入： 6 3 1 2 3 5 1 3 2 5 4 5 5 4 3 2 1 3 3 1 2 4 2 3 1 4 5 5 1 2 3 4 输出： YES YES NO NO NO NO 注意： 在第一个测试用例中，排列已经排序。 在第二个测试用例中，我们可以选择索引i=2，因为1<3且3>2，得到[1, 2, 3, 5, 4]。然后，我们可以选择索引i=4，因为3<5且5>4，得到[1, 2, 3, 4, 5]。 在第三个测试用例中，可以证明无法对排列进行排序。