Consider an array $a$ of $n$ positive integers.

You may perform the following operation:

select two indices $l$ and $r$ ($1 \leq l \leq r \leq n$), then

decrease all elements $a_l, a_{l + 1}, \dots, a_r$ by $1$.

Let's call $f(a)$ the minimum number of operations needed to change array $a$ into an array of $n$ zeros.

Determine if for all permutations$^\dagger$ $b$ of $a$, $f(a) \leq f(b)$ is true.

$^\dagger$ An array $b$ is a permutation of an array $a$ if $b$ consists of the elements of $a$ in arbitrary order. For example, $[4,2,3,4]$ is a permutation of $[3,2,4,4]$ while $[1,2,2]$ is not a permutation of $[1,2,3]$.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$) — the length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — description of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case, print "YES" (without quotes) if for all permutations $b$ of $a$, $f(a) \leq f(b)$ is true, 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
3
4
2 3 5 4
3
1 2 3
4
3 1 3 2
Output
YES
YES
NO


-----Note-----

In the first test case, we can change all elements to $0$ in $5$ operations. It can be shown that no permutation of $[2, 3, 5, 4]$ requires less than $5$ operations to change all elements to $0$.

In the third test case, we need $5$ operations to change all elements to $0$, while $[2, 3, 3, 1]$ only needs $3$ operations.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Constructive algorithms


Solutions:
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	I = list(map(int, input().split()))
	i = 0
	check = True
	while i < n - 1 and I[i] <= I[i + 1]:
		i += 1
	while i < n - 1:
		if I[i] < I[i + 1]:
			check = False
			break
		i += 1
	if check:
		print('YES')
	else:
		print('NO')


import sys
input = lambda : sys.stdin.readline().rstrip()

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	f = 0
	idx = -1
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			idx = i
			break
	if idx == -1:
		return 1
	for i in range(idx, n - 1):
		if a[i] < a[i + 1]:
			f = 1
	if f:
		return 0
	return 1
for __ in range(int(input())):
	print('YES' if solve() else 'NO')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	inc = True
	flag = True
	for i in range(1, n):
		if a[i] == a[i - 1]:
			continue
		if a[i] > a[i - 1]:
			if inc:
				continue
			else:
				flag = False
				break
		elif inc:
			inc = False
		else:
			continue
	if flag:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline

def solution(a, n):
	reverse = False
	current = a[0]
	for i in range(1, n):
		if reverse is False:
			if a[i] < current:
				reverse = True
		if reverse is True:
			if a[i] > current:
				print('NO')
				return
		current = a[i]
	print('YES')
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	solution(a, n)


def main():
	for _ in range(int(input())):
		print('YES' if problem() else 'NO')

def problem():
	n = int(input())
	arr = list(map(int, input().split()))
	mode = 'increasing'
	for i in range(1, n):
		if mode == 'increasing':
			if arr[i] < arr[i - 1]:
				mode = 'decreasing'
		elif arr[i] > arr[i - 1]:
			return False
	return True
import sys
input = sys.stdin.readline
sys.exit(main())


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	v = max(arr)
	mid = 0
	for i in range(n):
		if arr[i] == v:
			mid = i
			break
	for i in range(n - 1):
		if i < mid and arr[i] > arr[i + 1]:
			return 'NO'
		if i >= mid and arr[i] < arr[i + 1]:
			return 'NO'
	return 'YES'
for _ in range(int(input())):
	print(solve())


import sys
input = sys.stdin.readline

def solve(n, a):
	if n == 1:
		return 'YES'
	sol = True
	(mx_idx, mx) = (0, a[0])
	for (i, a_i) in enumerate(a):
		if a_i > mx:
			(mx, mx_idx) = (a_i, i)
	for i in range(0, mx_idx - 1):
		if a[i] > a[i + 1]:
			sol = False
			break
	for i in range(mx_idx, n - 1):
		if a[i] < a[i + 1]:
			sol = False
			break
	return 'YES' if sol else 'NO'
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(solve(n, a))


t = int(input())
ans = [''] * t
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	isUp = True
	isGood = True
	prev = a[0]
	for j in range(1, n):
		if isUp and prev > a[j]:
			isUp = False
		elif not isUp and prev < a[j]:
			isGood = False
		prev = a[j]
	if isGood:
		ans[i] = 'YES'
	else:
		ans[i] = 'NO'
for i in range(t):
	print(ans[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())
tests = inp()
for j in range(0, tests):
	n = inp()
	x = inlt()
	resul = 'YES'
	y = 0
	z = 0
	min_val = -1
	for i in range(1, len(x) - 1):
		if x[i] < x[i - 1]:
			min_val = x[i]
		if min_val != -1 and min_val < x[i + 1]:
			resul = 'NO'
	print(resul)


import sys
input = sys.stdin.readline
import math
import copy
import collections
from collections import deque
import heapq
import itertools
from collections import defaultdict
from collections import Counter
for x in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	cur = arr[0]
	dec = False
	works = True
	for i in arr:
		if i < cur:
			dec = True
		if i > cur and dec:
			print('NO')
			works = False
			break
		cur = i
	if works:
		print('YES')


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def get_int():
	return int(sys.stdin.readline())

def get_string():
	return sys.stdin.readline().strip()

def solve(arr):
	M = max(arr)
	count = arr[0]
	for i in range(1, len(arr)):
		count += max(0, arr[i] - arr[i - 1])
	return count == M
t = get_int()
for _ in range(t):
	n = get_int()
	arr = list(map(int, get_string().split()))
	sys.stdout.write('YES\n' if solve(arr) else 'NO\n')


import sys
input = sys.stdin.readline
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = False
	for i in range(n - 1):
		if arr[i] > arr[i + 1]:
			count = True
		if arr[i] < arr[i + 1] and count:
			print('NO')
			break
	else:
		print('YES')


import itertools
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())
for _ in range(inp()):
	n = inp()
	arr = [k for (k, _) in itertools.groupby(inlt())]
	ans = True
	for i in range(1, len(arr) - 1):
		if arr[i] < arr[i - 1] and arr[i] < arr[i + 1]:
			ans = False
			break
	print('YES' if ans else 'NO')


def optimal_reduction(n, seq):
	prefix_non_decreasing = 1
	suffix_non_increasing = 1
	i = 0
	while i < n - 1 and seq[i] <= seq[i + 1]:
		prefix_non_decreasing += 1
		i += 1
	i = n - 2
	while i > -1 and seq[i + 1] <= seq[i]:
		suffix_non_increasing += 1
		i -= 1
	if prefix_non_decreasing + suffix_non_increasing >= n:
		return 'YES'
	else:
		return 'NO'
t = int(input())
test_cases = [(int(input()), tuple(map(int, input().split()))) for _ in range(t)]
answers = [optimal_reduction(n, seq) for (n, seq) in test_cases]
for a in answers:
	print(a)


def solve(p):
	state = 0
	prev = -1
	for v in p:
		if state == 0:
			if v >= prev:
				state = 0
			else:
				state = 1
		else:
			if v > prev:
				return False
			pass
		prev = v
	return True

def main():
	n = int(input())
	for _ in range(n):
		n = int(input())
		points = [int(x) for x in input().split()]
		print('YES' if solve(points) else 'NO')
		pass
	pass
main()


import sys
from collections import Counter, defaultdict, deque
from math import gcd, sqrt, ceil, log

def li():
	return [int(i) for i in sys.stdin.readline().split()]

def si():
	return sys.stdin.readline().split()

def ii():
	return int(sys.stdin.readline())

def ip():
	return input()
for tastcas in range(int(input())):
	n = ii()
	a = li()
	f = 0
	i = 0
	if n < 3:
		print('YES')
		continue
	while i < n - 1:
		if a[i + 1] < a[i]:
			f = 1
			break
		i += 1
	while i < n - 1:
		if a[i + 1] > a[i]:
			f = 2
			break
		i += 1
	if f == 2:
		print('NO')
	else:
		print('YES')


def check(l):
	a = 0
	b = len(l) - 1
	while a != b:
		if l[a] <= l[a + 1] or l[b] <= l[b - 1]:
			if l[a] <= l[a + 1]:
				a = a + 1
			else:
				b = b - 1
		else:
			return False
	return True
li = []
t = int(input())
for i in range(t):
	n = int(input())
	lis = input()
	l = lis.split()
	for i in range(len(l)):
		l[i] = int(l[i])
	li.append(check(l))
for i in li:
	if i:
		print('YES')
	else:
		print('NO')


t = int(input())
res = []
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = [a[0]]
	lastItem = a[0]
	for i in range(1, n):
		if a[i] != lastItem:
			b.append(a[i])
			lastItem = a[i]
	isOK = True
	for i in range(1, len(b) - 1):
		if b[i - 1] > b[i] < b[i + 1]:
			isOK = False
			break
	if isOK:
		res.append('YES')
	else:
		res.append('NO')
for r in res:
	print(r)


import math

def solve():
	n = int(input())
	increasing = True
	previous = -math.inf
	numbers = list(map(int, input().split()))
	answer = 'YES'
	for x in numbers:
		if increasing:
			if x >= previous:
				pass
			else:
				increasing = False
		elif x <= previous:
			pass
		else:
			answer = 'NO'
			break
		previous = x
	print(answer)
T = int(input())
for _ in range(T):
	solve()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	data = list(map(int, input().split()))
	max_value = max(data)
	max_idx = data.index(max_value)
	diff = []
	flag = True
	for i in range(max_idx):
		if data[i + 1] - data[i] < 0:
			flag = False
	for i in range(max_idx, n - 1):
		if data[i + 1] - data[i] > 0:
			flag = False
	if flag:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline

def s(nums):
	if sorted(nums) == nums:
		return True
	elif sorted(nums, reverse=True) == nums:
		return True
	else:
		return False
for __ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	idx = lst.index(max(lst))
	lst1 = lst[:idx + 1]
	lst2 = lst[idx:]
	if s(lst1) and s(lst2):
		print('YES')
	else:
		print('NO')


out = []
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	if max(a) == min(a):
		out.append('YES')
		continue
	if a == sorted(a) or a == sorted(a, reverse=True):
		out.append('YES')
		continue
	ok = 'YES'
	p0 = a.index(max(a))
	for i in range(p0, n - 1):
		if a[i + 1] > a[i]:
			ok = 'NO'
	for i in range(p0 - 1):
		if a[i + 1] < a[i]:
			ok = 'NO'
	out.append(ok)
for i in out:
	print(i)


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	i = 1
	while i < n and A[i] >= A[i - 1]:
		i += 1
	while i < n and A[i] <= A[i - 1]:
		i += 1
	if i == n:
		print('YES')
	else:
		print('NO')
t = int(input())
while t != 0:
	solve()
	t -= 1


t = int(input())
ans = []
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	flag = 1
	M = a[0]
	for i in range(1, n - 1):
		M = max(a[i], M)
		if M > a[i] and a[i] < a[i + 1]:
			flag = 0
			break
	if flag:
		ans.append('YES')
	else:
		ans.append('NO')
for i in range(t):
	print(ans[i])


t = int(input())
for i in range(0, t):
	n = int(input())
	s = [int(x) for x in input().split()]
	m = max(s)
	j = s.index(m)
	f = 0
	for l in range(0, j):
		if s[l] > s[l + 1]:
			f = 1
			break
	for k in range(j + 1, n - 1):
		if s[k] < s[k + 1]:
			f = 1
			break
	if f:
		print('NO')
	else:
		print('YES')


def trim(L):
	if L[0] == 0:
		return trim(L[1:])
	else:
		return L

def make(k):
	import itertools
	list1 = list(k)
	list1 = [g for (g, _) in itertools.groupby(list1)]
	return list1

def fn(L):
	k = trim(L)
	k = trim(k[::-1])
	if len(k) < 3:
		return 'YES'
	for i in range(len(k) - 2):
		if k[i] > k[i + 1] and k[i + 1] < k[i + 2]:
			return 'NO'
	k = make(k)
	if len(k) < 3:
		return 'YES'
	for i in range(len(k) - 2):
		if k[i] > k[i + 1] and k[i + 1] < k[i + 2]:
			return 'NO'
	return 'YES'
a = int(input())
op = []
for i in range(a):
	b = int(input())
	c = input()
	c = c.split()
	c = [int(o) for o in c]
	op.append(fn(c))
for t in op:
	print(t)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	i = a.index(max(a))
	b = a[:i]
	c = a[i:]
	if b == sorted(b) and c == sorted(c)[::-1]:
		print('YES')
	else:
		print('NO')


def peak(arr):
	res = 0
	cur = arr[0]
	flag = 0
	for i in arr:
		if flag == 0 and i < cur:
			flag = 1
			res = cur
		elif flag == 1 and i > cur:
			return 'NO'
		cur = i
	return 'YES'
t = int(input())
for test in range(t):
	n = int(input())
	arr = [int(_) for _ in input().split()]
	print(peak(arr))


t = int(input())

def f(a, n):
	maxVal = 0
	maxI = 0
	reachedMax = False
	for i in range(0, n - 1):
		if not reachedMax and a[i + 1] < a[i]:
			reachedMax = True
		if reachedMax and a[i + 1] > a[i]:
			return 'NO'
	return 'YES'
for i in range(t):
	n = int(input())
	ls = list(map(int, input().split()))
	print(f(ls, n))


def solve():
	t = 1
	t = int(input())
	while t:
		t -= 1
		n = int(input())
		a = [int(x) for x in input().split()]
		max_b = max(a)
		max_a = 0
		for i in range(n - 1):
			if a[i] > a[i + 1]:
				max_a += a[i] - a[i + 1]
		max_a += a[n - 1]
		if max_a <= max_b:
			print('YES')
		else:
			print('NO')
solve()


import sys

def solve():
	for _ in range(int(input())):
		input()
		a = list(map(int, input().split()))
		s = a.index(max(a))
		(L, R) = (a[:s], a[s:])
		if L == sorted(L) and R == sorted(R, reverse=True):
			print('YES')
		else:
			print('NO')

def main():
	solve()
main()


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	i = 0
	while i + 1 < n and l[i + 1] >= l[i]:
		i = i + 1
	while i + 1 < n and l[i + 1] <= l[i]:
		i = i + 1
	if i + 1 == n:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = input().split()
	arr = [int(i) for i in arr]
	increaseMode = True
	isMin = True
	for i in range(len(arr) - 1):
		if increaseMode and arr[i + 1] < arr[i]:
			increaseMode = False
		if not increaseMode and arr[i + 1] > arr[i]:
			isMin = False
			break
	print('YES' if isMin else 'NO')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	idx = a.index(max(a))
	if a[:idx] == sorted(a[:idx]) and a[idx:] == sorted(a[idx:], reverse=True):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = 1
	for i in range(1, n):
		if l[i - 1] > l[i]:
			s = 0
		elif l[i - 1] < l[i] and s == 0:
			print('NO')
			break
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	err = 0
	for i in range(1, n):
		if arr[i] < arr[i - 1] and err == 0:
			err += 1
		if arr[i] > arr[i - 1] and err == 1:
			print('NO')
			err += 1
			break
	if err != 2:
		print('YES')


t = int(input())
while t > 0:
	n = int(input())
	list0 = list(map(int, input().split()))
	index = list0.index(max(list0))
	list1 = list0[:index + 1]
	list2 = list0[index:]
	temp = []
	for num in list2:
		temp.append(num)
	list2.sort()
	list2.reverse()
	if sorted(list1) == list1 and list2 == temp:
		print('YES')
	else:
		print('NO')
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	index = a.index(max(a))
	a1 = a[:index + 1]
	a2 = a[index:]
	temp = list(a2)
	a2.sort(reverse=True)
	if sorted(a1) == a1 and a2 == temp:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	t -= 1
	n = int(input())
	inc = 0
	dec = 0
	flag = False
	arr = list(map(int, input().split()))
	for i in range(1, n):
		if arr[i] > arr[i - 1]:
			if dec == 0:
				inc = 1
			else:
				flag = True
				break
		elif arr[i] < arr[i - 1]:
			dec = 1
	if flag:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	flag = 0
	ans = 0
	for j in range(n - 1):
		if flag == 0:
			if a[j + 1] >= a[j]:
				continue
			else:
				flag = 1
		if flag == 1:
			if a[j + 1] <= a[j]:
				continue
			else:
				ans = 1
				break
	if ans == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	a = [0]
	flag = True
	a = list(map(int, input().split()))
	ind = n
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			ind = i
			break
	for i in range(ind, n - 1):
		if a[i] < a[i + 1]:
			flag = False
			break
	print('YES') if flag else print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	arr = input()
	arr = arr.split()
	a = [int(x) for x in arr]
	mx = max(a)
	mx_ind = a.index(mx)
	a0 = a[:mx_ind]
	b0 = a0.copy()
	b0.sort()
	a1 = a[mx_ind:]
	b1 = a1.copy()
	b1.sort(reverse=True)
	if a0 == b0 and a1 == b1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	i = 1
	while i < n and arr[i] >= arr[i - 1]:
		i += 1
	while i < n and arr[i] <= arr[i - 1]:
		i += 1
	print('YES' if i == n else 'NO')


for pratyush in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a.copy()
	b.sort()
	(x, y, i, f) = (0, n - 1, 0, 1)
	while x <= y:
		if a[x] == b[i]:
			x += 1
			i += 1
		elif a[y] == b[i]:
			y -= 1
			i += 1
		else:
			f = 0
			break
	if f:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a_sort = sorted(a)
	if a == a_sort or a == a_sort[::-1]:
		print('YES')
		continue
	idx = a.index(max(a))
	if sorted(a[:idx]) == a[:idx] and sorted(a[idx:])[::-1] == a[idx:]:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	_seq = [int(x) for x in input().split(' ')]
	seq = [_seq[0]]
	for s in _seq[1:]:
		if s != seq[-1]:
			seq.append(s)
	ans = 'YES'
	for i in range(1, len(seq) - 1):
		if seq[i - 1] > seq[i] < seq[i + 1]:
			ans = 'NO'
			break
	print(ans)


for _ in range(int(input())):
	size = int(input())
	array = tuple(map(int, input().strip().split(' ')))
	(left, right) = (-1, -1)
	for idx in range(0, len(array) - 1):
		if array[idx + 1] >= array[idx]:
			continue
		left = idx
		break
	for idx in range(len(array) - 1, -1, -1):
		if array[idx - 1] >= array[idx]:
			continue
		right = idx
		break
	yes = left >= right or left == -1 or right == -1
	print('YES' if yes else 'NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = max(l)
	i = l.index(m)
	s = 'NO'
	if l[:i] == sorted(l[:i]) and l[i:n] == sorted(l[i:n])[::-1]:
		s = 'YES'
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	list1 = list(map(int, input().split()))
	indx = list1.index(max(list1))
	if list1[:indx] == sorted(list1[:indx]) and list1[indx:] == sorted(list1[indx:], reverse=True):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	inp = list(map(int, input().split()))
	maxdex = inp.index(max(inp))
	flag = 0
	for i in range(1, maxdex):
		if inp[i] < inp[i - 1]:
			flag = 1
			break
	if flag == 0:
		for i in range(maxdex + 1, n - 1):
			if inp[i] < inp[i + 1]:
				flag = 1
				break
	if flag == 1:
		print('NO')
	else:
		print('YES')


def solve():
	b = int(input())
	c = list(map(int, input().split(maxsplit=b - 1)))
	count = 0
	for x in range(1, b - 1):
		if c[x - 1] > c[x] and count == 0:
			count += 1
		if c[x] < c[x + 1] and count == 1:
			print('NO')
			count += 1
			break
	if count != 2:
		print('YES')
a = int(input())
for _ in range(a):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	first = False
	second = False
	for i in range(n - 1):
		if not first and arr[i] > arr[i + 1]:
			first = True
		elif first and arr[i] < arr[i + 1]:
			second = True
		else:
			pass
	if second:
		print('NO')
	else:
		print('YES')


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	i = 0
	while i < n - 1 and arr[i + 1] >= arr[i]:
		i += 1
	if i == n - 1:
		print('YES')
		return
	j = 1
	while j < n and arr[n - j - 1] >= arr[n - j]:
		j += 1
	if j == n:
		print('YES')
		return
	if i + j + 1 >= n:
		print('YES')
	else:
		print('NO')
t = int(input())
for _ in range(t):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	sequence = [int(num) for num in input().split()]
	num_changes = 0
	is_increasing = True
	for i in range(n - 1):
		if is_increasing and sequence[i] > sequence[i + 1]:
			is_increasing = False
			num_changes += 1
		elif not is_increasing and sequence[i] < sequence[i + 1]:
			is_increasing = True
			num_changes += 1
	if num_changes >= 2:
		print('NO')
	else:
		print('YES')


for f in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	da = True
	br = n - 1
	dosad = a[0]
	for i in range(n - 1):
		if dosad > a[i + 1]:
			br = i + 1
			dosad = a[i + 1]
			break
		dosad = a[i + 1]
	for i in range(br, n - 1):
		if dosad < a[i + 1]:
			da = False
			break
		dosad = a[i + 1]
	if not da:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	mx = max(arr)
	pos_mx = arr.index(mx)
	arr21 = arr[:pos_mx]
	arr22 = arr[pos_mx:]
	arr211 = sorted(arr21)
	arr222 = sorted(arr22, reverse=True)
	if arr211 == arr21 and arr222 == arr22:
		print('YES')
		continue
	print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	array = list(map(int, input().split()))
	array.insert(0, -1)
	array.append(-1)
	glav = True
	flag = True
	j = 1
	while flag:
		if array[j] >= array[j - 1]:
			j += 1
		else:
			flag = False
	for k in range(j, n + 1):
		if array[k] <= array[k - 1]:
			continue
		else:
			glav = False
			break
	if glav:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	T = list(map(int, input().split()))
	Ind = T.index(max(T))
	if T[:Ind] == sorted(T[:Ind]) and T[Ind:] == sorted(T[Ind:], reverse=True):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	if n < 3:
		print('YES')
	else:
		flag = False
		for i in range(n - 1):
			if a[i] > a[i + 1]:
				flag = True
			if flag and a[i] < a[i + 1]:
				print('NO')
				break
		else:
			print('YES')


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	lmax = l.index(max(l))
	lleft = l[:lmax]
	lright = l[lmax + 1:]
	if lleft == sorted(lleft) and lright == sorted(lright, reverse=True):
		print('YES')
	else:
		print('NO')
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	flag = 0
	for i in range(0, n - 1):
		if arr[i] > arr[i + 1]:
			flag = 1
		if flag == 1 and arr[i] < arr[i + 1]:
			flag = 2
			break
	if flag == 2:
		print('NO')
	else:
		print('YES')


for z in range(0, int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 'YES'
	x = -1
	for i in range(0, n - 1):
		if l[i] > l[i + 1]:
			x = i
			break
	if x != -1:
		for j in range(x + 1, n - 1):
			if l[j + 1] > l[j]:
				ans = 'NO'
				break
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	j = 1
	while j < len(arr) and arr[j] >= arr[j - 1]:
		j = j + 1
	while j < len(arr) and arr[j] <= arr[j - 1]:
		j = j + 1
	if j == n:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	i = lst.index(max(lst))
	l1 = lst[:i + 1]
	l2 = lst[i:]
	l2 = l2[::-1]
	if sorted(l1) == l1 and l2 == sorted(l2):
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	n = int(input())
	lst = [int(i) for i in input().split()]
	inc = 0
	dec = 0
	f = 0
	for i in range(1, n):
		if lst[i] > lst[i - 1]:
			if dec == 0:
				inc = 1
			else:
				f = 1
				break
		elif lst[i] < lst[i - 1]:
			dec = 1
	if f:
		print('NO')
	else:
		print('YES')


import sys
v = int(sys.stdin.readline())
for _ in range(v):
	n = int(sys.stdin.readline())
	p = list(map(int, input().split()))[:n]
	sol = 'YES'
	c = False
	for i in range(1, n):
		if p[i - 1] > p[i]:
			c = True
		elif p[i - 1] < p[i] and c:
			sol = 'NO'
			break
	sys.stdout.write(str(sol) + '\n')


from mimetypes import suffix_map
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	prefix_len = 1
	while prefix_len < n and arr[prefix_len - 1] <= arr[prefix_len]:
		prefix_len += 1
	suf_len = 1
	j = n - 2
	while suf_len < n and arr[n - suf_len - 1] >= arr[n - suf_len]:
		suf_len += 1
	if prefix_len + suf_len >= n:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(s, f) = (0, 0)
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			s = 1
		elif a[i] < a[i + 1] and s == 1:
			print('NO')
			f = 1
			break
	if f == 0:
		print('YES')


testCase = int(input())
for i in range(testCase):
	n = int(input())
	arr = list(map(int, input().split()))
	ind = 0
	while ind + 1 < n and arr[ind] <= arr[ind + 1]:
		ind += 1
	while ind + 1 < n and arr[ind] >= arr[ind + 1]:
		ind += 1
	if ind + 1 == n:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	u = 0
	v = 0
	for j in range(1, n - 1):
		if a[j] < a[j - 1]:
			u += 1
			v = j
			break
	for k in range(v, n - 1):
		if a[k] < a[k + 1]:
			u += 1
			break
	if u >= 2:
		print('NO')
	else:
		print('YES')


def check(n, arr, narr):
	(l, r) = (0, n - 1)
	i = 0
	while l <= r:
		if arr[l] == narr[i]:
			l += 1
			i += 1
		elif arr[r] == narr[i]:
			r -= 1
			i += 1
		else:
			return False
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	narr = arr.copy()
	narr.sort()
	if check(n, arr, narr):
		print('YES')
	else:
		print('NO')


def solve():
	n = int(input())
	lst = list(map(int, input().split(' ')))
	flag = False
	for i in range(n - 1):
		if flag and lst[i + 1] > lst[i]:
			print('NO')
			return
		if lst[i + 1] < lst[i]:
			flag = True
	print('YES')
t = int(input())
while t:
	t -= 1
	solve()


def check():
	b = [a[0]]
	for i in range(1, len(a)):
		if a[i] != b[-1]:
			b.append(a[i])
	if len(b) <= 1:
		return True
	if b[1] < b[0]:
		for i in range(1, len(b)):
			if b[i] > b[i - 1]:
				return False
		return True
	j = 0
	while j < len(b) - 1 and b[j] < b[j + 1]:
		j += 1
	for k in range(j, len(b) - 1):
		if b[k] < b[k + 1]:
			return False
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	print('YES' if check() else 'NO')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().rstrip().split()))
	count = False
	for i in range(n - 1):
		if arr[i] > arr[i + 1]:
			count = True
		if arr[i] < arr[i + 1] and count:
			print('NO')
			break
	else:
		print('YES')