Indirect Sort
Contest: CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 800
Tags: constructive algorithms, implementation, math

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.

Input format:
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$$$.

Output format:
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).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
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

Example output:
Yes
Yes
No
No
No
No
Yes

Editorial:
We claim that we can sort the array if and only if $$$a_1 = 1$$$.
Necessity
We can notice that index $$$1$$$ cannot be affected by any swap operation.
Let's see what happens to the value $$$1$$$. According to the definition of the operation, it can either increase or be swapped. In order to be increased, there must exist some $$$k$$$ such that $$$1 > a_k$$$, but since $$$1$$$ is the minimum possible value, it will never be true as other values in array $$$a$$$ can only increse as well. Since index $$$1$$$ can not be affected by a swap operation and $$$a_1>1$$$, we conclude that if $$$a_1 \neq 1$$$, the answer is No.
Sufficiency
Let's focus on the second operation. Since we have $$$a_1 = 1$$$, we can always choose $$$i=1$$$ and the operation then turns into picking some pair $$$2 \le j < k \le n$$$ and swapping $$$a_j$$$ with $$$a_k$$$. It's trivial to see we can always sort with such an operation.