## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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 ${a}_{1},{a}_{2},\dots ,{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).
• 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\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}\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\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, $\left[1,2,3\right]$ 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 $\left[1,2,3\right]$, 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 $\left[1,2,6,7,4,5,3\right]$.
• 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 $\left[1,2,6,7,9,5,3\right]$.
• Choose $i=2,j=5,k=7$. Since ${a}_{2}\le {a}_{7}$, swap ${a}_{5}$ and ${a}_{7}$, the array then becomes $\left[1,2,6,7,3,5,9\right]$.
• Choose $i=2,j=4,k=6$. Since ${a}_{2}\le {a}_{6}$, swap ${a}_{4}$ and ${a}_{6}$, the array then becomes $\left[1,2,6,5,3,7,9\right]$.
• Choose $i=1,j=3,k=5$. Since ${a}_{1}\le {a}_{5}$, swap ${a}_{3}$ and ${a}_{5}$, the array then becomes $\left[1,2,3,5,6,7,9\right]$, 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