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

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

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


-----Examples-----

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
Output
Yes
Yes
No
No
No
No
Yes


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

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Implementation

Constructive algorithms


Solutions:
lines = int(input())
x = []
c = []
for i in range(lines):
	l = input()
	x = list(input().split())
	if x[0] == '1':
		c.append('Yes')
	elif x[0] != '1':
		c.append('No')
for n in c:
	print(n)


for s in [*open(0)][2::2]:
	(x, *a) = map(int, s.split())
	print('YNeos'[x > min(a)::2])


import sys
input = iter(sys.stdin.read().splitlines()).__next__
TC = int(input())
for tc in range(TC):
	N = int(input())
	A = list(map(int, input().split()))
	print('Yes' if A[0] == 1 else 'No')


cishu = int(input())
result = []
while cishu:
	cishu -= 1
	n = int(input())
	c = input().split()
	if c[0] == '1':
		result.append('Yes')
	else:
		result.append('No')
for i in result:
	print(i)


def judge(ls):
	if ls[0] == 1:
		return 'Yes'
	else:
		return 'No'
t = int(input())
ans = []
for i in range(t):
	a = int(input())
	ls = list(map(int, input().split()))
	ans.append(judge(ls))
for i in range(t):
	print(ans[i])


def ans(n, a):
	if a[0] != 1:
		return 'No'
	else:
		return 'Yes'
t = int(input())
r = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = ans(n, a)
	r.append(c)
for i in range(t):
	print(r[i])


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
test_cases = inp()
inp_arr = []
for i in range(test_cases):
	num = inp()
	nums = inlt()
	inp_arr.append(nums)

def findResult(nums):
	if nums[0] == min(nums):
		result = 'Yes'
	else:
		result = 'No'
	return result
result = [findResult(cheeses) for cheeses in inp_arr]
for m in result:
	print(m)


turns = int(input())
result = []
for _ in range(turns):
	n = int(input())
	array = list(map(int, input().split()))
	if array[0] == 1:
		result.append('Yes')
	else:
		result.append('No')
for res in result:
	print(res)


test = int(input())
answer = list()
for _ in range(test):
	nums = int(input())
	arrnums = list(map(int, input().split()))
	if min(arrnums) == arrnums[0]:
		answer.append('Yes')
	else:
		answer.append('No')
for i in answer:
	print(i)


n = int(input())
a = []
for i in range(n):
	m = int(input())
	f = input()
	if f[0] == '1' and f[1] == ' ':
		a.append('Yes')
	else:
		a.append('No')
for i in range(n):
	print(a[i], end='\n')


testcases = int(input())
for _ in range(testcases):
	n = int(input())
	numbers = list(map(int, input().split()))
	if min(numbers) == numbers[0]:
		print('Yes')
	else:
		print('No')


t = int(input())
ans = []
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	if nums[0] > min(nums):
		ans.append(0)
	else:
		ans.append(1)
for i in ans:
	print('Yes' if i else 'No')


import sys
from bisect import bisect_left, bisect_right
from heapq import heapify, heappush, heappop
from collections import deque
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for _ in range(ii()):
	n = ii()
	arr = il()
	if arr[0] == 1:
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	n = int(input())
	arr = input().split()
	if arr[0] != '1':
		print('No')
	else:
		print('Yes')


t = int(input())
while t > 0:
	n = int(input())
	a = input().split()
	if a[0] == '1':
		print('Yes')
	else:
		print('No')
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if l[0] == 1:
		print('Yes')
	else:
		print('No')


from math import ceil
import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = get_arr()
	if a[0] == 1:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = input()
	k = list(map(int, input().split()))
	print('YNeos'[k[0] != 1::2])


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	if s[0] == min(s):
		print('Yes')
	else:
		print('No')


def work():
	n = int(input())
	s = input().split(' ')
	if s[0] == '1':
		print('Yes')
	else:
		print('No')
t = int(input())
for i in range(t):
	work()


test = int(input())
for k in range(test):
	n = int(input())
	a = list(map(int, input().split()))
	if a[0] == 1:
		print('Yes')
	else:
		print('No')


a = int(input())
for _ in range(a):
	b = int(input())
	c = list(map(int, input().split()))
	if c[0] == min(c):
		print('Yes')
	else:
		print('No')


for i in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	if min(list1) == list1[0]:
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if a[0] != 1:
		print('No')
	else:
		print('Yes')


import os, sys, io, math
from array import array
from math import *
from collections import Counter, defaultdict
I = lambda : [*map(int, sys.stdin.readline().split())]
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
for _ in range(IN()):
	(n, l) = (IN(), I())
	print('Yes' if l[0] == 1 else 'No')


t = int(input())
for _ in range(t):
	v = int(input())
	temp = input().split()
	h = [int(j) for j in temp]
	smallest = 100
	for i in h:
		if i < smallest:
			smallest = i
	if h[0] == smallest:
		print('Yes')
	else:
		print('No')


a = int(input())
for _ in range(a):
	s = int(input())
	mas = list(map(int, input().split()))
	if mas[0] == 1:
		print('Yes')
	else:
		print('No')


T = int(input())
for _ in range(T):
	n = int(input())
	a = input().split(' ')
	if a[0] == '1':
		print('Yes')
	else:
		print('No')


for t in range(int(input())):
	n = input()
	s = input()
	if s.startswith('1 '):
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	n = int(input())
	xs = [int(x) for x in input().split()]
	flag = False
	if xs[0] != 1:
		print('No')
	else:
		print('Yes')


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(a, n):
	return 'Yes' if a[0] == 1 else 'No'
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(a, n))