You are given an array $a[0 \dots n-1]$ of $n$ integers. This array is called a "valley" if there exists exactly one subarray $a[l \dots r]$ such that:

$0 \le l \le r \le n-1$,

$a_l = a_{l+1} = a_{l+2} = \dots = a_r$,

$l = 0$ or $a_{l-1} > a_{l}$,

$r = n-1$ or $a_r < a_{r+1}$.

Here are three examples:

The first image shows the array [$3, 2, 2, 1, 2, 2, 3$], it is a valley because only subarray with indices $l=r=3$ satisfies the condition.

The second image shows the array [$1, 1, 1, 2, 3, 3, 4, 5, 6, 6, 6$], it is a valley because only subarray with indices $l=0, r=2$ satisfies the codition.

The third image shows the array [$1, 2, 3, 4, 3, 2, 1$], it is not a valley because two subarrays $l=r=0$ and $l=r=6$ that satisfy the condition.

You are asked whether the given array is a valley or not.

Note that we consider the array to be indexed from $0$.


-----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 2\cdot10^5$) — the length of the array.

The second line of each test case contains $n$ integers $a_i$ ($1 \leq a_i \leq 10^9$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases is smaller than $2\cdot10^5$.


-----Output-----

For each test case, output "YES" (without quotes) if the array is a valley, and "NO" (without quotes) otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).


-----Examples-----

Input
6
7
3 2 2 1 2 2 3
11
1 1 1 2 3 3 4 5 6 6 6
7
1 2 3 4 3 2 1
7
9 7 4 6 9 9 10
1
1000000000
8
9 4 4 5 9 4 9 10
Output
YES
YES
NO
YES
YES
NO


-----Note-----

The first three test cases are explained in the statement.

Source: codeforces | Difficulty: EASY
Tags: Amortized analysis

Implementation


Solutions:
from itertools import *
for s in [*open(0)][2::2]:
	a = [k for (k, g) in groupby(map(int, s.split()))]
	print('YNEOS'[sum((x > y < z for (x, y, z) in zip([2000000000.0] + a, a, a[1:] + [2000000000.0]))) > 1::2])


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 len(nums) <= 2:
		return 'YES'
	is_dec = True
	for i in range(1, len(nums)):
		if not is_dec and nums[i] < nums[i - 1]:
			return 'NO'
		if is_dec and nums[i] > nums[i - 1]:
			is_dec = False
	return 'YES'
result = [findResult(cheeses) for cheeses in inp_arr]
for m in result:
	print(m)


import sys
input = sys.stdin.readline
case = int(input())
for c in range(case):
	n = int(input())
	a = list(map(int, input().split()))
	flag = True
	valley = True
	for i in range(1, n):
		if flag and a[i] > a[i - 1]:
			flag = False
		if not flag and a[i] < a[i - 1]:
			valley = False
			break
	if valley:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline

def solution():
	T = int(input())
	for t in range(T):
		N = int(input())
		h = list(map(int, input().split()))
		if N == 1:
			print('YES')
		else:
			answer = 'YES'
			down = 1
			for i in range(1, N):
				if h[i - 1] > h[i] and down == 0:
					answer = 'NO'
					break
				elif h[i - 1] < h[i] and down == 1:
					down = 0
			print(answer)
solution()


from sys import stdin
from itertools import groupby

def readint():
	return int(stdin.readline())

def readarray(typ):
	return list(map(typ, stdin.readline().split()))

def readmatrix(n):
	M = []
	for _ in range(n):
		row = readarray(int)
		assert len(row) == n
		M.append(row)
	return M

def mult(M, v):
	n = len(M)
	return [sum((M[i][j] * v[j] for j in range(n))) for i in range(n)]

def solve(arr):
	res = [i[0] for i in groupby(arr)]
	if len(res) == 1:
		print('YES')
		return
	p = res.index(min(res))
	for i in range(0, p):
		if res[i] < res[i + 1]:
			print('NO')
			return
	for q in range(p, len(res) - 1):
		if res[q] > res[q + 1]:
			print('NO')
			return
	print('YES')
	return
t = readint()
for _ in range(t):
	n = readint()
	arr = readarray(int)
	solve(arr)


import sys
from collections import *
sys.setrecursionlimit(10 ** 5)
itr = (line for line in sys.stdin.read().strip().split('\n'))
INP = lambda : next(itr)

def ni():
	return int(INP())

def nl():
	return [int(_) for _ in INP().split()]

def solve(n, a):
	isIncreasing = False
	if n == 1:
		print('YES')
		return
	for i in range(n - 1):
		if a[i + 1] > a[i]:
			isIncreasing = True
		if isIncreasing:
			if a[i + 1] < a[i]:
				print('NO')
				return
	print('YES')
t = ni()
for case in range(t):
	n = ni()
	a = nl()
	solve(n, a)


def solve(arr):
	i = 0
	j = len(arr) - 1
	while i != j:
		if arr[i] >= arr[i + 1]:
			i += 1
		elif arr[j] >= arr[j - 1]:
			j -= 1
		else:
			break
	return 'YES' if i == j else 'NO'

def main():
	ans = []
	for _ in range(int(input())):
		input()
		ans.append(solve(list(map(int, input().split()))))
	print(*ans, sep='\n')
main()


import sys
from sys import stdin
import heapq
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
input = sys.stdin.readline
t = int(input())
res = []
for _ in range(t):
	n = int(input())
	lis = list(map(int, input().split()))
	(k, s) = (inf, True)
	for i in lis:
		if k < i and s == True:
			(k, s) = (i, False)
			continue
		if k >= i and s == True:
			k = i
			continue
		if s == False and k > i:
			s = -1
			continue
		k = i
	res.append('YES' if s != -1 else 'NO')
print(*res, sep='\n')


def solve(arr):
	befo = arr[0]
	isInkreasin = False
	for each in arr:
		diff = each - befo
		if isInkreasin and diff < 0:
			print('NO')
			return
		elif not isInkreasin and diff > 0:
			isInkreasin = True
		befo = each
	print('YES')
t = int(input())
problems = []
for i in range(t):
	n = int(input())
	l = []
	for each in input().split():
		l.append(int(each))
	problems.append(l)
for each in problems:
	solve(each)


import sys
input = sys.stdin.readline

def get_answ():
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		return 'YES'
	mn = min(arr)
	idx = arr.index(mn)
	i = idx - 1
	j = idx + 1
	while i >= 0:
		if arr[i] >= arr[i + 1]:
			i -= 1
		else:
			return 'NO'
	while j <= n - 1:
		if arr[j] >= arr[j - 1]:
			j += 1
		else:
			return 'NO'
	return 'YES'

def main():
	for _ in range(int(input())):
		answ = get_answ()
		print(answ)
main()


import sys

def input():
	return sys.stdin.readline().rstrip('\r\n')

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


def calc(l):
	if len(l) == 1:
		return 'YES'
	q = [0]
	for i in range(1, len(l)):
		if l[i - 1] > l[i]:
			q.append(-1)
		elif l[i - 1] < l[i]:
			q.append(1)
		else:
			q.append(0)
	i = q.count(1)
	if i == 0:
		return 'YES'
	i = q.index(1)
	if -1 in q[i:]:
		return 'NO'
	return 'YES'
l = []
for _ in range(int(input())):
	input()
	l.append(calc(list(map(int, input().split()))))
print('\n'.join(l))


from math import inf
from sys import stdin, stdout
t = int(stdin.readline().strip())
for _ in range(t):
	n = int(stdin.readline().strip())
	arr = list(map(int, stdin.readline().split()))
	arr.append(inf)
	answer = 0
	last_start = 0
	for (idx, num) in enumerate(arr):
		if num == arr[last_start]:
			continue
		elif arr[last_start] < arr[last_start - 1] and arr[last_start] < num:
			answer += 1
			last_start = idx
			if answer > 1:
				break
		else:
			last_start = idx
	print('YES' if answer == 1 else 'NO')


t = int(input())

def solve():
	n = int(input())
	nums = [int(x) for x in input().split()]
	increasing = False
	p = 99999999999
	for num in nums:
		if increasing:
			if num < p:
				print('NO')
				return
		elif num > p:
			increasing = True
		p = num
	print('YES')
for _ in range(t):
	solve()


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


def hasValley(nums):
	i = 0
	valley = 0
	while i < n:
		j = i
		if i == 0 or nums[i] < nums[i - 1]:
			while j < n and nums[j] == nums[i]:
				j += 1
			if j == n or nums[j - 1] < nums[j]:
				valley += 1
			i = j
		else:
			i += 1
	return valley == 1
t = int(input())
res = []
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	if hasValley(nums):
		res.append('YES')
	else:
		res.append('NO')
for r in res:
	print(r)


def remove_adjacent(nums):
	return [a for (a, b) in zip(nums, nums[1:] + [not nums[-1]]) if a != b]

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


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	min_a = min(a)
	ind_min = a.index(min_a)
	f = a[:ind_min]
	l = a[ind_min:]
	if f == sorted(f)[::-1] and l == sorted(l):
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	a = int(input())
	k = [int(i) for i in input().split()]
	b = k[:]
	b.sort()
	m = 0
	c = b[:]
	c.reverse()
	if b == k or c == k:
		print('YES')
		m = 3
	else:
		for j in range(a - 1):
			if k[j] < k[j + 1]:
				mn = k[j]
				b = j
				break
		k = k[b:]
		for j in range(len(k) - 1):
			if k[j] > k[j + 1]:
				print('NO')
				m = 1
				break
	if m == 0:
		print('YES')


t = int(input())
for _ in range(t):
	num = int(input())
	arr = list(map(int, input().split()))
	index = -1
	for i in range(len(arr) - 1):
		if arr[i] < arr[i + 1]:
			index = i
			break
	if index == -1:
		print('YES')
		continue
	A = arr[index + 1:]
	B = sorted(A)
	if A == B:
		print('YES')
	else:
		print('NO')


n = int(input())
answers = []
for i in range(n):
	array_len = int(input())
	array = list(map(int, input().split()))
	up = 0
	down = 0
	check = 0
	for j in range(1, array_len):
		if array[j] > array[j - 1]:
			up += 1
		elif array[j] < array[j - 1]:
			down += 1
			if up > 0:
				check += 1
				break
	if check > 0:
		answers.append('NO')
	else:
		answers.append('YES')
for ans in answers:
	print(ans)


import sys
input = sys.stdin.readline

def solve():
	(N, A) = (int(input()), list(map(int, input().split())))
	c = 0
	L = [A[0]]
	for i in range(1, N):
		if A[i] != L[-1]:
			L.append(A[i])
	for i in range(0, len(L)):
		if (i == 0 or L[i - 1] > L[i]) and (i == len(L) - 1 or L[i] < L[i + 1]):
			c += 1
	if c == 1:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	solve()


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = l[:l.index(min(l)) + 1]
	b = l[l.index(min(l)) + 1:]
	if sorted(a, reverse=True) == a and sorted(b) == b:
		print('YES')
	else:
		print('NO')


is_true = True

def state_f(arr):
	ans = 'dol'
	for (l, n) in zip(arr, arr[1:]):
		if l < n:
			ans = 'gora'
		elif ans == 'gora':
			if l > n:
				return 'NO'
	return 'YES'
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 'dol'
	yn = 'YES'
	print(state_f(arr=arr))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ss = l.copy()
	if l == sorted(ss) or l == sorted(ss, reverse=True):
		print('YES')
	else:
		s = 'Down'
		t = 'YES'
		for _ in range(1, len(l)):
			if s == 'Down':
				if l[_] > l[_ - 1]:
					s = 'Up'
			elif l[_] < l[_ - 1]:
				t = 'NO'
				break
		print(t)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	m = min(arr)
	pos_m = arr.index(m)
	ans = False
	if max(arr) == m:
		print('YES')
		continue
	arr_a = arr[:pos_m + 1]
	arr_b = arr[pos_m:n]
	if arr_a == sorted(arr_a, reverse=True) and arr_b == sorted(arr_b):
		print('YES')
	else:
		print('NO')


def answer(points):
	left = points[0]
	valley = 0
	for i in range(1, len(points)):
		if valley == 0:
			if points[i] > left:
				valley += 1
			left = points[i]
		elif points[i] < left:
			return 'NO'
		else:
			left = points[i]
	return 'YES'
test = int(input())
for i in range(test):
	size = int(input())
	points = list(map(int, input().split()))
	print(answer(points))


def DA(a):
	i = 0
	xn = True
	while i != n - 1:
		i += 1
		if a[i] != a[i - 1]:
			if a[i] < a[i - 1]:
				xn = False
			break
	if xn:
		while i != n - 1:
			i += 1
			if a[i] < a[i - 1]:
				return 'NO'
	else:
		while i != n - 1:
			i += 1
			if a[i] > a[i - 1]:
				break
		while i != n - 1:
			i += 1
			if a[i] < a[i - 1]:
				return 'NO'
	return 'YES'
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(DA(a))


t = int(input())
answer1 = 'YES'
answer2 = 'NO'
zero = 0
one = 1
two = 2

def main():
	for q in range(t):
		nums = int(input())
		array = list(map(int, input().split()))
		if nums == one:
			print(answer1)
		else:
			guess = one
			while guess < nums and array[guess] <= array[guess - one]:
				guess = guess + one
			while guess < nums and array[guess] >= array[guess - one]:
				guess = guess + one
			if not guess == nums:
				print(answer2)
			else:
				print(answer1)
main()


ip = int(input())
for i in range(ip):
	n = int(input())
	l = list(map(int, input().split()))
	copy = l.copy()
	if l == sorted(copy):
		print('YES')
	elif l == sorted(copy, reverse=True):
		print('YES')
	else:
		direc = 'below'
		val = 'YES'
		for i in range(1, len(l)):
			if direc == 'below':
				if l[i] > l[i - 1]:
					direc = 'above'
			elif l[i] < l[i - 1]:
				val = 'NO'
				break
		print(val)


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


for _ in int(input()) * ' ':
	n = int(input())
	l = list(map(int, input().split()))
	k = sorted(l.copy())
	if k == l:
		print('YES')
	else:
		z = k[0]
		i = 0
		a = 1
		q = '-'
		while i < n - 1:
			if q == '-':
				if l[i] == z:
					q = '+'
				elif l[i] >= l[i + 1]:
					i += 1
				else:
					a = 0
					break
			elif l[i] <= l[i + 1]:
				i += 1
			else:
				a = 0
				break
		if a:
			print('YES')
		else:
			print('NO')


def valley(a):
	mn = min(a)
	f = a.index(mn)
	rev = f
	ant = mn
	while rev >= 0:
		if a[rev] < ant:
			print('NO')
			return
		ant = a[rev]
		rev -= 1
	rev = f
	ant = mn
	while rev < len(a):
		if a[rev] < ant:
			print('NO')
			return
		ant = a[rev]
		rev += 1
	print('YES')
	return ()

def main():
	n = int(input())
	for i in range(n):
		input()
		a = [int(x) for x in input().split()]
		valley(a)
main()


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


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


t = int(input(''))
aas = [0] * t
for j in range(t):
	x = int(input(''))
	y = input('').split(' ')
	y = [int(z) for z in y]
	v = y[0]
	firstup = -1
	lastdown = -1
	for i in range(x - 1):
		if firstup == -1 and y[i + 1] > y[i]:
			firstup = i
		if y[i + 1] < y[i]:
			lastdown = i
	v1 = lastdown < firstup
	v2 = lastdown == -1 or firstup == -1
	aas[j] = ('NO', 'YES')[v1 or v2]
for a in aas:
	print(a)


for _ in (input() for _ in range(int(input()))):
	(xs, counter, last, valley) = (list(map(int, input().split())), 0, 10 ** 10, False)
	for (i, x) in enumerate(xs):
		if valley:
			if x == last:
				continue
			if x > last:
				counter += 1
			valley = False
		if x < last:
			valley = True
		last = x
	print(['NO', 'YES'][counter + valley == 1])


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(len(arr) - 1):
		if arr[i] < arr[i + 1]:
			if arr[i:] == sorted(arr[i:]):
				print('YES')
			else:
				print('NO')
			break
	else:
		print('YES')


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


t = int(input())
for _ in range(t):
	n = int(input())
	ps = list(map(int, input().split()))
	last_i = 0
	bad = False
	br = False
	for i in range(n - 1):
		last_i = i
		if ps[i] < ps[i + 1]:
			br = True
			break
	if not br:
		print('YES')
		continue
	for i in range(last_i, n - 1):
		if ps[i] > ps[i + 1]:
			bad = True
			break
	if bad:
		print('NO')
	else:
		print('YES')


def oi():
	a = input().split()
	a = [int(i) for i in a]
	valley = 0
	history = a[0]
	previous = ''
	for i in a:
		if i < history:
			previous = 'down'
			history = i
		elif i > history:
			if previous != 'up':
				valley += 1
			previous = 'up'
			history = i
	if previous != 'up':
		valley += 1
	return 'YES' if valley == 1 else 'NO'
for i in range(int(input())):
	input()
	print(oi())


from sys import stdout
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	flag = True
	(recmin, gt) = (arr[0], 1)
	for i in range(1, n):
		if gt:
			if arr[i - 1] < arr[i]:
				gt = 0
		elif arr[i - 1] > arr[i]:
			flag = False
	if flag:
		print('YES')
	else:
		print('NO')


def sol(n, l):
	m = min(l)
	x = l.index(m)
	for i in range(x + 1, n):
		if l[i] < l[i - 1]:
			return 'NO'
	for i in range(x - 1, -1, -1):
		if l[i + 1] > l[i]:
			return 'NO'
	return 'YES'
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(sol(n, l))


def boolvalley(li, n):
	if n == 1:
		return True
	j = 0
	for i in range(n - 1):
		if li[i] == li[i + 1]:
			j += 1
		else:
			break
	if j == n - 1:
		return True
	if li[j] > li[j + 1]:
		x = j
		y = j + 1
		f = 0
		while y < n:
			if li[y] > li[x]:
				f = 1
				break
			x += 1
			y += 1
		if f == 0:
			return True
		else:
			while y < n:
				if li[y] < li[x]:
					return False
				x += 1
				y += 1
			return True
	else:
		x = j
		y = j + 1
		while y < n:
			if li[x] > li[y]:
				return False
			y += 1
			x += 1
		return True
t = int(input())
while t > 0:
	n = int(input())
	li = list(map(int, input().split()))
	if boolvalley(li, n):
		print('YES')
	else:
		print('NO')
	t -= 1


import sys
input = sys.stdin.readline
ins = lambda : input().rstrip()
ini = lambda : int(input().rstrip())
inm = lambda : map(int, input().rstrip().split())
inl = lambda : list(map(int, input().split()))
out = lambda x, s='\n': print(s.join(map(str, x)))
t = ini()
for _ in range(t):
	n = ini()
	a = inl()
	b = []
	for i in a:
		if b != [] and i == b[-1]:
			continue
		b.append(i)
	count = 0
	x = len(b)
	if x == 1:
		print('YES')
		continue
	for i in range(x):
		if (i == 0 or b[i - 1] > b[i]) and (i == x - 1 or b[i + 1] > b[i]):
			count += 1
	print('YES' if count == 1 else 'NO')


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


N = int(input())
for _ in range(N):
	input()
	arr = list(map(int, input().split()))
	falling = True
	valley = True
	for i in range(1, len(arr)):
		if falling and arr[i] > arr[i - 1]:
			falling = False
		if not falling and arr[i] < arr[i - 1]:
			valley = False
			break
	if valley:
		print('YES')
	else:
		print('NO')


def runCase():
	n = int(input())
	array = list(map(int, input().split()))
	left = 0
	right = 1
	while right < n:
		if array[left] < array[right]:
			break
		right += 1
		left += 1
	else:
		return 'YES'
	while right < n:
		if array[left] > array[right]:
			break
		right += 1
		left += 1
	else:
		return 'YES'
	left = 0
	right = n - 1
	while left < right:
		if left + 1 < right:
			if array[left] < array[left + 1]:
				break
		if right - 1 > left:
			if array[right] < array[right - 1]:
				break
		left += 1
		right -= 1
	else:
		return 'YES'
	return 'NO'
tests = int(input())
for _ in range(tests):
	print(runCase())


for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	if n == 1:
		print('YES')
	elif num == sorted(num):
		print('YES')
	else:
		m = min(num)
		f = 0
		flag = 1
		for i in range(n - 1):
			if num[i] == m:
				f = 1
			if f == 0:
				if num[i + 1] > num[i]:
					flag = 0
					break
				else:
					flag = 1
			elif num[i + 1] < num[i]:
				flag = 0
				break
		if flag:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	st = l[0]
	cs = 1
	p = l[0]
	pi = 0
	for i in range(1, n):
		if l[i] <= p:
			p = l[i]
			pi = i
			continue
		else:
			break
	for i in range(pi, n):
		if l[i] < p:
			cs = 0
			break
		else:
			p = l[i]
	if cs == 1:
		print('YES')
	else:
		print('NO')


from sys import maxsize

def solve(arr, n):
	arr.append(10 ** 9 + 7)
	ans = 1
	is_increasing = False
	for i in range(0, n):
		if ans == 1 and arr[i] < arr[i + 1]:
			ans = 2
		if ans == 2 and arr[i] > arr[i + 1]:
			return 'NO'
	return 'YES'
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(solve(arr, n))


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


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
import math
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

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

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = inp()
for i in range(t):
	n = inp()
	l = li()
	f = 0
	k = 0
	if n == 1:
		print('YES')
	elif len(set(l)) == 1:
		print('YES')
	else:
		for i in range(1, n):
			if i == 1:
				if l[i] <= l[i - 1]:
					k = 1
				elif l[i] > l[i - 1]:
					f += 1
			elif k == 1:
				if l[i] > l[i - 1]:
					f += 1
					k = 0
				elif l[i] <= l[i - 1]:
					k = 1
			elif l[i] < l[i - 1]:
				k = 1
		if k == 1:
			f += 1
		if f == 1:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	bot = min(a)
	ans = True
	for i in range(a.index(bot) + 1, n):
		if a[i] < a[i - 1]:
			ans = False
	for i in range(a.index(bot)):
		if a[i + 1] > a[i]:
			ans = False
	if ans:
		print('YES')
	else:
		print('NO')


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


t = int(input())
result = []
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arc1 = arr.copy()
	arc2 = arr.copy()
	if arc1.sort() == arr:
		result.append('YES')
	elif arc2.sort(reverse=True) == arr:
		result.append('YES')
	else:
		c = 0
		flag = 0
		for j in range(1, n):
			if c == 0:
				if arr[j] > arr[j - 1]:
					c = 1
			elif arr[j] < arr[j - 1]:
				flag = 1
				break
		if flag == 1:
			result.append('NO')
		else:
			result.append('YES')
for i in result:
	print(i)


def dolina(a: list):
	n = len(a)
	p = 0
	f = 0
	pow = 0
	while f < len(a) and pow == 0:
		if f == 0 or a[f - 1] > a[f]:
			l = a[f]
			while f < n - 1 and a[f] == l:
				f += 1
			if f == n - 1 or a[f - 1] < a[f]:
				p += 1
				f += 1
		else:
			f += 1
	if p == 1:
		return True
	return False
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if dolina(a):
		print('YES')
	else:
		print('NO')


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


for t in range(int(input())):
	m = int(input())
	lis = list(map(int, input().split()))
	(f, x) = (0, 1)
	for i in range(m - 1):
		if f == 0:
			if lis[i + 1] > lis[i]:
				f = 1
			else:
				f = 0
		elif lis[i + 1] < lis[i]:
			print('NO')
			x = 0
			break
		else:
			f = 1
			continue
	if x:
		print('YES')


t = int(input())

def checkif(actual):
	c = 0
	for i in range(len(actual)):
		if (i == 0 or actual[i - 1] > actual[i]) and (i == len(actual) - 1 or actual[i] < actual[i + 1]):
			c += 1
	return c == 1
for i in range(t):
	n = int(input())
	ar = input().split()
	ar = [int(u) for u in ar]
	s = []
	p = None
	if len(ar) == 1:
		print('YES')
	else:
		for i in ar:
			if i != p:
				s.append(i)
			p = i
		if checkif(s):
			print('YES')
		else:
			print('NO')


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


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


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


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = min(l)
	x = l.index(m)
	f = True
	for i in range(x + 1, n):
		if l[i] < l[i - 1]:
			f = False
			break
	if f:
		for i in range(x - 1, -1, -1):
			if l[i + 1] > l[i]:
				f = False
				break
	if f:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	inp = list(map(int, input().split()))
	arr = [inp[0]]
	for i in inp[1:]:
		if i != arr[-1]:
			arr.append(i)
	cnt = 0
	for i in range(len(arr)):
		if (i == 0 or arr[i - 1] > arr[i]) and (i == len(arr) - 1 or arr[i + 1] > arr[i]):
			cnt += 1
	print('YES') if cnt == 1 else print('NO')


t = int(input())
for x in range(t):
	n = int(input())
	nums = [int(i) for i in input().split(' ')]
	if n == 1:
		print('YES')
		continue
	a = [nums[i + 1] - nums[i] for i in range(n - 1)]
	answer = 'YES'
	now = None
	for i in a:
		if i > 0:
			if now == None:
				now = 'up'
			elif now == 'down':
				now = 'up'
		elif i < 0:
			if now == None:
				now = 'down'
			elif now == 'up':
				answer = 'NO'
				break
	print(answer)


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


import sys
T = int(input())
for tc in range(T):
	ai = int(input())
	ai_li = list(map(int, sys.stdin.readline().split()))
	status = 0
	idx = 0
	for i in range(1, len(ai_li)):
		if ai_li[i] - ai_li[i - 1] > 0:
			status = 1
			idx = i - 1
			break
	if status == 0:
		print('YES')
	else:
		checker = True
		for j in range(idx + 1, len(ai_li)):
			if ai_li[j] - ai_li[j - 1] < 0:
				checker = False
		if checker:
			print('YES')
		else:
			print('NO')


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


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = min(l)
	if l == sorted(l):
		print('YES')
	else:
		for i in range(n):
			if l[i] == x:
				break
		s1 = l[0:i + 1]
		s2 = l[i:]
		s1 = s1[::-1]
		if s1 == sorted(s1) and s2 == sorted(s2):
			print('YES')
		else:
			print('NO')


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	conf = 0
	prev = a[0]
	e = 1
	if len(a) == 1:
		ans.append('YES')
		continue
	while prev == a[e]:
		if e + 1 < len(a):
			e += 1
		else:
			ans.append('YES')
			break
	if e + 1 == len(a) and a[0] == a[-1]:
		continue
	if a[e] > prev:
		conf += 1
	prev = a[-1]
	c = len(a) - 2
	while prev == a[c]:
		if c >= 0:
			c -= 1
		else:
			break
	if a[c] > prev:
		conf += 1
	if conf == 2:
		ans.append('NO')
		continue
	bottom = -1000
	for j in range(e, c + 2):
		if a[j] < a[j - 1]:
			bottom = a[j]
		elif a[j] == a[j - 1] and bottom == a[j - 1]:
			bottom = a[j]
		elif bottom == a[j - 1]:
			conf += 1
	if conf == 1:
		ans.append('YES')
	else:
		ans.append('NO')
print(*ans, sep='\n')


def f():
	T = int(input())
	for _ in range(T):
		_ = input()
		nums = [int(c) for c in input().split()]
		b = solve(nums)
		print('YES' if b else 'NO')

def solve(nums):
	n = len(nums)
	distincts = []
	for i in range(n):
		if i == 0 or nums[i] != distincts[-1]:
			distincts.append(nums[i])
	valley_cnt = 0
	N = len(distincts)
	for i in range(N):
		if (i == 0 or distincts[i - 1] > distincts[i]) and (i == N - 1 or distincts[i] < distincts[i + 1]):
			valley_cnt += 1
	return valley_cnt == 1
f()


for _ in range(int(input())):
	n = int(input())
	num = [int(x) for x in input().split()]
	checker = r = False
	for i in range(n - 1):
		if num[i + 1] > num[i]:
			checker = True
		if checker and num[i + 1] < num[i]:
			r = True
	if r:
		print('NO')
	else:
		print('YES')


def solution():
	n = int(input())
	nums = [int(i) for i in input().split()]
	i = 1
	while i < n and nums[i] <= nums[i - 1]:
		i += 1
	while i < n and nums[i] >= nums[i - 1]:
		i += 1
	if i == n:
		print('YES')
	else:
		print('NO')
t = int(input())
while t:
	solution()
	t -= 1


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


def solve(l, a):
	for i in range(a):
		if l[i] < l[i + 1]:
			return 'NO'
	for i in range(a, len(l) - 1):
		if l[i] > l[i + 1]:
			return 'NO'
	return 'YES'
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = l.index(min(l))
	print(solve(l, a))


t = int(input())
for essa in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	last = -420
	b = []
	b.append(2000000000)
	for essa in a:
		if essa != last:
			b.append(essa)
		last = essa
	b.append(2000000000)
	m = len(b)
	cnt = 0
	for i in range(1, m):
		if b[i] < b[i - 1] and b[i] < b[i + 1]:
			cnt += 1
	if cnt == 1:
		print('YES')
	else:
		print('NO')


import math
t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	i = 0
	error = False
	while i < n - 1:
		if lst[i] >= lst[i + 1]:
			i += 1
		else:
			break
	j = i
	while j < n - 1:
		if lst[j] <= lst[j + 1]:
			j += 1
		else:
			error = True
			break
	print('NO' if error else 'YES')


for _ in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	l = 0
	r = len(list1) - 1
	while l != r:
		if list1[l] >= list1[l + 1]:
			l += 1
		elif list1[r] >= list1[r - 1]:
			r -= 1
		else:
			break
	if l == r:
		print('YES')
	else:
		print('NO')


import math
for _ in range(int(input())):
	a = int(input())
	z = list(map(int, input().split()))
	t = z.index(min(z))
	if sorted(z, reverse=False) == z:
		print('YES')
	elif sorted(z, reverse=True) == z:
		print('YES')
	elif sorted(z[:t + 1], reverse=True) == z[:t + 1] and sorted(z[t:]) == z[t:]:
		print('YES')
	else:
		print('NO')


t = int(input())
for h in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	f = 10 ** 10
	i = 0
	while i < n and f >= a[i]:
		f = a[i]
		i += 1
	g = 0
	if i < n:
		f = a[i]
		for j in range(i, n):
			if f > a[j]:
				g = 1
			f = a[j]
	if g == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
answers = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	spad = True
	pod = False
	for i in range(len(a) - 1):
		if a[i + 1] <= a[i] and spad:
			None
		elif a[i + 1] > a[i] and spad:
			spad = False
			pod = True
		elif a[i + 1] >= a[i] and pod:
			None
		else:
			answers.append('NO')
			break
	else:
		answers.append('YES')
for i in answers:
	print(i)


def solution():
	n = int(input()) + 2
	a = [2 * 10 ** 5] + [int(num) for num in input().split()] + [2 * 10 ** 5]
	cnt = 0
	valley = False
	for i in range(1, n):
		if a[i] < a[i - 1]:
			valley = True
			continue
		if a[i] == a[i - 1] and valley:
			continue
		if a[i] > a[i - 1] and valley:
			valley = False
			cnt += 1
			if cnt > 1:
				print('NO')
				return
	print('YES')

def main():
	t = int(input())
	while t:
		solution()
		t -= 1
main()


def fun(n, li):
	(l, r) = (0, 0)
	for i in range(1, n):
		if li[i - 1] < li[i]:
			l = 1
		if l == 1 and li[i - 1] > li[i]:
			r = 1
			return False
	return True
for i in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	if fun(n, li) == 1:
		print('YES')
	else:
		print('NO')