From a hidden array A of length N, Stack constructs an array B of length N such that:
For all i (1 ≤ i ≤ N), B_{i}=\max(A_{1},A_{2},\ldots,A_{i}) or B_{i}=\min(A_{1},A_{2},\ldots,A_{i}).

For the given array B of length N, Stack wants you to check whether a possible array A exists or not.

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follow.
- The first line of each test case contains an integer N - the length of the array B.
- The second line of each test case contains N space-separated integers B_{1},B_{2},\ldots,B_{N} representing the array B.

------ Output Format ------ 

For each test case, output in a single line YES if A exists, otherwise print NO.

You may print each character of the string in uppercase or lowercase (for example, the strings YES, yEs, yes, and yeS will all be treated as identical).

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ B_{i} ≤ 10^{5}$
- Sum of $N$ over all test cases does not exceed $10^{5}$.

----- Sample Input 1 ------ 
3
1
343
4
1 1 2 3
3
1 3 2

----- Sample Output 1 ------ 
YES
YES
NO

----- explanation 1 ------ 
Test case $1$: The only possible array is $A=[343]$.

Test case $2$: One possible array is $A=[1,1,2,3]$. In this case $B_{i} = max(A_{1}, A_{2}, \ldots, A_{i})$ satisfies for all $1 ≤ i ≤ 4$.

Test case $3$: It can be proven that there exists no $A$ from which we can obtain the given array $B$.

----- Sample Input 2 ------ 
2
5
1 1 1 1 1 
5
1 2 1 2 1

----- Sample Output 2 ------ 
YES
YES

----- explanation 2 ------ 
Test case $1$: The only possible array is $A=[1,1,1,1,1]$.

Test case $2$: One possible array is $A=[1,2,1,1,1]$. 
In this case,
- $B_{1}=A_{1}$
- $B_{2}=\max(A_{1},A_{2})$
- $B_{3}=\min(A_{1},A_{2},A_{3})$
- $B_{4}=\max(A_{1},A_{2},A_{3},A_{4})$
- $B_{5}=\min(A_{1},A_{2},A_{3},A_{4},A_{5})$

Difficulty: EASY
Tags: Constructive algorithms

Starter code:

Solutions:
import math
for _ in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	flag = 1
	max1 = 0
	min1 = math.inf
	for i in range(N):
		if L[i] < max1 and L[i] > min1:
			flag = 0
			break
		max1 = max(max1, L[i])
		min1 = min(min1, L[i])
	if flag:
		print('YES')
	else:
		print('NO')


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	max = float('-inf')
	min = float('inf')
	flag = True
	for i in range(n):
		if a[i] > max:
			max = a[i]
		if a[i] < min:
			min = a[i]
		if a[i] != min and a[i] != max:
			flag = False
	if flag:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if len(a) == 1:
		print('YES')
	else:
		(mi, ma, b) = (a[0], a[0], 0)
		for i in range(1, n):
			if mi <= a[i] or ma >= a[i]:
				if mi <= a[i]:
					mi = a[i]
				if ma >= a[i]:
					ma = a[i]
			else:
				b += 1
				break
		if b == 0:
			print('YES')
		else:
			print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	if len(b) == 1:
		print('YES')
	else:
		mini = b[0]
		maxi = b[0]
		bt = 0
		for i in range(1, n):
			if b[i] <= mini or b[i] >= maxi:
				if b[i] <= mini:
					mini = b[i]
				if b[i] >= maxi:
					maxi = b[i]
			else:
				bt = 1
				break
		if bt == 0:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	mini = arr[0]
	maxi = arr[0]
	found = False
	for i in arr:
		if i >= maxi:
			maxi = i
		elif i <= mini:
			mini = i
		else:
			found = True
			break
	if not found:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	mx = b[0]
	mn = b[0]
	f = 1
	for j in b:
		if j > mx:
			mx = j
		elif j < mn:
			mn = j
		elif j > mn and j < mx:
			f = 0
			break
	if f == 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	lst = [int(x) for x in input().split()]
	min = lst[0]
	max = lst[0]
	flag = 1
	for i in lst:
		if i <= min:
			min = i
		elif i >= max:
			max = i
		else:
			flag = 0
			break
	if flag:
		print('YES')
	else:
		print('NO')


t = int(input())
for tc in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	x = b[0]
	y = b[0]
	d = 0
	for j in range(len(b)):
		if b[j] >= x:
			x = b[j]
		elif b[j] <= y:
			y = b[j]
		elif b[j] < x:
			d = -1
	if d == -1:
		print('NO')
	else:
		print('YES')


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


def possibleArray(B):
	minSoFar = B[0]
	maxSoFar = B[0]
	for i in range(1, len(B)):
		if B[i] >= maxSoFar:
			maxSoFar = B[i]
		elif B[i] <= minSoFar:
			minSoFar = B[i]
		if B[i] != minSoFar and B[i] != maxSoFar:
			return 'NO'
	return 'YES'
for _ in range(int(input())):
	N = int(input())
	B = list(map(int, input().split()))
	print(possibleArray(B))


n = int(input())
for i in range(n):
	a = int(input())
	l = list(map(int, input().split()))
	s = -9999999
	k = 999999999
	if len(l) == 1:
		print('YES')
	else:
		for j in l:
			if j > s:
				s = j
			if j < k:
				k = j
			if j != s and j != k:
				print('NO')
				break
		else:
			print('YES')


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


t = int(input())
while t > 0:
	n = int(input())
	list1 = list(map(int, input().split()))
	f = 0
	if len(list1) == 1:
		print('YES')
	else:
		mi = list1[0]
		ma = list1[0]
		for i in range(0, len(list1)):
			if list1[i] <= mi:
				mi = list1[i]
			elif list1[i] >= ma:
				ma = list1[i]
			elif list1[i] < ma:
				f = -1
				break
		if f == -1:
			print('NO')
		else:
			print('YES')
	t = t - 1


for i in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	p = True
	(min1, max1) = (b[0], b[0])
	for i in b:
		if min1 < i < max1:
			p = False
		elif i < min1:
			min1 = i
		elif i > max1:
			max1 = i
	if p:
		print('YES')
	else:
		print('NO')


for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(mine, maxe) = (arr[0], arr[0])
	possible = True
	for ele in arr:
		if mine < ele < maxe:
			possible = False
		elif ele < mine:
			mine = ele
		elif ele > maxe:
			maxe = ele
	if possible:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	if n == 1:
		print('YES')
		continue
	(ma, mi) = (x[0], x[0])
	f = True
	for i in x[1:]:
		if i >= ma:
			ma = i
		elif i <= mi:
			mi = i
		else:
			f = False
			break
	print('YES') if f else print('NO')


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	(maxa, mina) = (a[0], a[0])
	ans = 'YES'
	for i in range(1, n):
		if a[i] >= maxa:
			maxa = a[i]
		elif a[i] <= mina:
			mina = a[i]
		else:
			ans = 'NO'
			break
	print(ans)


for _ in range(int(input())):
	N = int(input())
	B = [int(f) for f in input().split()]
	P = 'YES'
	Maximum = B[0]
	Minimum = B[0]
	for numbers in range(N):
		gap = Maximum - Minimum
		if B[numbers] - Maximum >= 0:
			Maximum = B[numbers]
		else:
			Minimum = B[numbers]
		if gap > Maximum - Minimum:
			P = 'NO'
			break
	print(P)


for _ in range(int(input())):
	maxi = float('-inf')
	mini = float('inf')
	n = int(input())
	b = list(map(int, input().split()))
	temp = 1
	for i in range(n):
		mini = min(mini, b[i])
		maxi = max(maxi, b[i])
		if b[i] == mini or b[i] == maxi:
			temp = 1
		else:
			temp = 0
			break
	if temp == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(min_v, max_v) = (float('inf'), float('-inf'))
	c = 0
	for i in range(n):
		min_v = min(min_v, a[i])
		max_v = max(max_v, a[i])
		if a[i] == min_v or a[i] == max_v:
			c += 1
		else:
			print('NO')
			break
	else:
		if c == n or n == 1:
			print('YES')
		else:
			print('NO')


def hiddenarray(N, nums):
	flag = 0
	slag = 0
	if N == 1:
		return 'YES'
	else:
		ma = float('-inf')
		mi = float('inf')
		for i in range(len(nums)):
			if nums[i] >= ma:
				ma = nums[i]
			if nums[i] <= mi:
				mi = nums[i]
			if nums[i] != mi and nums[i] != ma:
				return 'NO'
	return 'YES'
t = int(input())
while t > 0:
	N = int(input())
	nums = list(map(int, input().split()))
	print(hiddenarray(N, nums))
	t -= 1


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(high, low) = (arr[0], arr[0])
	for i in arr:
		if i <= low or i >= high:
			high = max(high, i)
			low = min(low, i)
		else:
			print('NO')
			break
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	mi = b[0]
	ma = b[0]
	ans = 'YES'
	for j in range(1, n):
		if b[j] < mi:
			mi = b[j]
		elif b[j] > ma:
			ma = b[j]
		elif b[j] < ma and b[j] > mi:
			ans = 'NO'
			break
	print(ans)


for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	mi = min(lst[:2])
	ma = max(lst[:2])
	for i in range(2, len(lst)):
		if lst[i] < ma and lst[i] > mi:
			print('NO')
			break
		mi = min(mi, lst[i])
		ma = max(ma, lst[i])
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	l = min(b[:2])
	h = max(b[:2])
	for i in b[2:]:
		if l < i < h:
			print('NO')
			break
		else:
			l = min(l, i)
			h = max(h, i)
	else:
		print('YES')


T = int(input())
for i in range(T):
	N = int(input())
	b = 0
	l = list(map(int, input().split()))
	(c, d) = (l[0], l[0])
	for j in range(1, N):
		if l[j] > c and l[j] < d:
			b = 1
			break
		c = min(c, l[j])
		d = max(d, l[j])
	if b == 1:
		print('NO')
	else:
		print('YES')


0
t = int(input())
for ni in range(t):
	n = int(input())
	b = [int(i) for i in input().split()]
	(minprev, maxprev) = (b[0], b[0])
	strike = 0
	for i in range(1, n):
		if b[i] <= minprev or b[i] >= maxprev:
			minprev = min(b[i], minprev)
			maxprev = max(b[i], maxprev)
		else:
			strike = 1
			print('NO')
			break
	if strike == 0:
		print('YES')


import os, sys, io, math
from re import *
from math import *
from array import *
from heapq import *
from bisect import *
from functools import *
from itertools import *
from statistics import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IP = lambda : map(int, input().split())
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
for _ in range(IN()):
	(n, l) = (IN(), I())
	if n == 1 or sorted(l) == l:
		print('YES')
	else:
		ok = 1
		(a, b) = (l[0], l[0])
		for i in range(1, n):
			if l[i] <= a or l[i] >= b:
				a = min(a, l[i])
				b = max(b, l[i])
			else:
				ok = 0
				print('NO')
				break
		if ok:
			print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	mx = arr[0]
	mn = arr[0]
	c = True
	for i in range(len(arr)):
		mx = max(mx, arr[i])
		mn = min(mn, arr[i])
		if arr[i] != mx and arr[i] != mn:
			c = False
			break
	if c == True:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	mini = l[0]
	maxi = l[0]
	f = True
	for i in range(n):
		maxi = max(maxi, l[i])
		mini = min(mini, l[i])
		if maxi != l[i] and mini != l[i]:
			f = False
			break
	print('YES') if f == True else print('NO')
	t -= 1


t = int(input())
for t in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	k = []
	maxI = l[0]
	minI = l[0]
	flag = True
	for i in range(len(l)):
		maxI = max(maxI, l[i])
		minI = min(minI, l[i])
		if l[i] != maxI and l[i] != minI:
			flag = False
			break
	print('YES' if flag == True else 'NO')


t = int(input())
while t != 0:
	n = int(input())
	list1 = list(map(int, input().split()))
	min1 = list1[0]
	max1 = list1[0]
	temp = 0
	for i in range(1, len(list1)):
		min1 = min(min1, list1[i])
		max1 = max(max1, list1[i])
		if list1[i] >= min1:
			if list1[i] < max1 and list1[i] != min1:
				print('NO')
				temp = 1
				break
			else:
				continue
		else:
			print('NO')
			temp = 1
			break
	if temp == 0:
		print('YES')
	t -= 1


from operator import mod
for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	min = li[0]
	max = li[0]
	i = 1
	while i != n:
		if li[i] > min and li[i] < max:
			break
		else:
			if li[i] < min:
				min = li[i]
			if li[i] > max:
				max = li[i]
			i += 1
	if i == n:
		print('YES')
	else:
		print('NO')


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


n = int(input())
for _ in range(n):
	x = int(input())
	l = list(map(int, input().split()))
	mini = 999999999
	maxi = -999999999
	for i in l:
		mini = min(mini, i)
		maxi = max(maxi, i)
		if i != mini and i != maxi:
			print('NO')
			break
	else:
		print('YES')


for tc in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	bmax = b[0]
	bmin = b[0]
	flag = 'yes'
	for i in range(n):
		if b[i] >= bmax:
			bmax = b[i]
		elif b[i] <= bmin:
			bmin = b[i]
		else:
			flag = 'fail'
			break
	if flag != 'fail':
		print('YES')
	else:
		print('NO')


def check(l):
	x = l[0]
	y = l[0]
	for i in range(n):
		if x > l[i]:
			x = l[i]
		if y < l[i]:
			y = l[i]
		if l[i] > x and l[i] < y:
			return False
	return True
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1 or n == 2:
		print('YES')
	else:
		s = check(l)
		if s:
			print('YES')
		else:
			print('NO')


n = int(input())
for i in range(n):
	l = []
	a = int(input())
	l = [int(x) for x in input().split()]
	max = 0
	count = 0
	for x in range(a):
		if max <= l[x]:
			max = l[x]
			count += 1
		elif l[x] <= min(l[:x]):
			count += 1
		else:
			break
	if count == a:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = l[0]
	y = l[0]
	t = 0
	for i in l[:]:
		if x < i < y:
			t = 1
			break
		x = min(x, i)
		y = max(y, i)
	if t:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	minn = l[0]
	maxx = l[0]
	t = 0
	for i in l[1:]:
		if i > minn and maxx > i:
			t = 1
			break
		minn = min(minn, i)
		maxx = max(maxx, i)
	if t:
		print('NO')
	else:
		print('YES')


n = int(input())
for j in range(n):
	l = int(input())
	s = list(map(int, input().split()))
	max = s[0]
	min = s[0]
	m = True
	for i in s:
		if i == max or i == min:
			continue
		elif i > max:
			max = i
		elif i < min:
			min = i
		else:
			m = False
	if m:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	mn = l[0]
	mx = l[0]
	for i in range(n):
		if l[i] >= mx:
			mx = l[i]
		elif l[i] <= mn:
			mn = l[i]
		else:
			print('NO')
			break
	else:
		print('YES')


n = int(input())
bs = []
for i in range(n):
	input()
	bs.append(list(map(int, input().split())))

def answer(b):
	for i in range(len(b)):
		if i == 0:
			maximum = b[i]
			minimum = b[i]
		maximum = b[i] if maximum < b[i] else maximum
		minimum = b[i] if minimum > b[i] else minimum
		if b[i] == maximum or b[i] == minimum:
			continue
		else:
			return 'NO'
	return 'YES'
for i in bs:
	print(answer(i))


for i in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	minn = b[0]
	maxx = b[0]
	for j in b:
		if minn >= j:
			minn = j
		elif maxx <= j:
			maxx = j
		else:
			print('NO')
			break
	else:
		print('YES')


def solve(n, lst):
	minimum = 100000
	maximum = 0
	f = 1
	for i in lst:
		if minimum < i < maximum:
			f = 0
		minimum = min(minimum, i)
		maximum = max(maximum, i)
	print('YES' if f == 1 else 'NO')
for _ in range(int(input())):
	n = int(input())
	solve(n, list(map(int, input().split())))


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


for _ in range(int(input())):
	N = int(input())
	B = list(map(int, input().split()))
	if len(B) <= 2:
		print('YES')
		continue
	M = max(B[:2])
	m = min(B[:2])
	c = 1
	for i in range(2, N):
		if B[i] < M and B[i] > m:
			c = 0
			break
		if B[i] < m:
			m = B[i]
		elif B[i] > M:
			M = B[i]
	if c == 1:
		print('YES')
	elif c == 0:
		print('NO')