[Solution] Indirect Sort Codeforces Solution

A. Indirect Sort

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a permutation 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ of size 𝑛$n$, where each integer from 1$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≤𝑖<𝑗<𝑘≤𝑛$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

Each test consists of multiple test cases. The first line contains a single integer 𝑡$t$ (1≤𝑡≤5000$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≤𝑛≤10$3\le n\le 10$) — the length of the array 𝑎$a$.

The second line contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤𝑛$1\le a_i\le n$, 𝑎𝑖≠𝑎𝑗$a_i\ne a_j$ if 𝑖≠𝑗$i\ne j$) — the elements of the array 𝑎$a$.

It is guaranteed that the sum of 𝑛$n$ over all test cases does not exceed 5⋅104$5\cdot {10}^4$.

Output

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).

Note

In the first test case, [1,2,3]$[1,2,3]$ is already sorted in non-descending order.

In the second test case, we can choose 𝑖=1,𝑗=2,𝑘=3$i=1,j=2,k=3$. Since 𝑎1≤𝑎3$a_1\le a_3$, swap 𝑎2$a_2$ and 𝑎3$a_3$, the array then becomes [1,2,3]$[1,2,3]$, which is sorted in non-descending order.

In the seventh test case, we can do the following operations successively:

• Choose 𝑖=5,𝑗=6,𝑘=7$i=5,j=6,k=7$. Since 𝑎5≤𝑎7$a_5\le a_7$, swap 𝑎6$a_6$ and 𝑎7$a_7$, the array then becomes [1,2,6,7,4,5,3]$[1,2,6,7,4,5,3]$.
• Choose 𝑖=5,𝑗=6,𝑘=7$i=5,j=6,k=7$. Since 𝑎5>𝑎7$a_5>a_7$, replace 𝑎5$a_5$ with 𝑎5+𝑎6=9$a_5+a_6=9$, the array then becomes [1,2,6,7,9,5,3]$[1,2,6,7,9,5,3]$.
• Choose 𝑖=2,𝑗=5,𝑘=7$i=2,j=5,k=7$. Since 𝑎2≤𝑎7$a_2\le a_7$, swap 𝑎5$a_5$ and 𝑎7$a_7$, the array then becomes [1,2,6,7,3,5,9]$[1,2,6,7,3,5,9]$.
• Choose 𝑖=2,𝑗=4,𝑘=6$i=2,j=4,k=6$. Since 𝑎2≤𝑎6$a_2\le a_6$, swap 𝑎4$a_4$ and 𝑎6$a_6$, the array then becomes [1,2,6,5,3,7,9]$[1,2,6,5,3,7,9]$.
• Choose 𝑖=1,𝑗=3,𝑘=5$i=1,j=3,k=5$. Since 𝑎1≤𝑎5$a_1\le a_5$, swap 𝑎3$a_3$ and 𝑎5$a_5$, the array then becomes [1,2,3,5,6,7,9]$[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