Vova's family is building the Great Vova Wall (named by Vova himself). Vova's parents, grandparents, grand-grandparents contributed to it. Now it's totally up to Vova to put the finishing touches.

The current state of the wall can be respresented by a sequence $a$ of $n$ integers, with $a_i$ being the height of the $i$-th part of the wall.

Vova can only use $2 \times 1$ bricks to put in the wall (he has infinite supply of them, however).

Vova can put bricks only horizontally on the neighbouring parts of the wall of equal height. It means that if for some $i$ the current height of part $i$ is the same as for part $i + 1$, then Vova can put a brick there and thus increase both heights by 1. Obviously, Vova can't put bricks in such a way that its parts turn out to be off the borders (to the left of part $1$ of the wall or to the right of part $n$ of it).

Note that Vova can't put bricks vertically.

Vova is a perfectionist, so he considers the wall completed when:  all parts of the wall has the same height;  the wall has no empty spaces inside it. 

Can Vova complete the wall using any amount of bricks (possibly zero)?


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of parts in the wall.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the initial heights of the parts of the wall.


-----Output-----

Print "YES" if Vova can complete the wall using any amount of bricks (possibly zero).

Print "NO" otherwise.


-----Examples-----
Input
5
2 1 1 2 5

Output
YES

Input
3
4 5 3

Output
NO

Input
2
10 10

Output
YES



-----Note-----

In the first example Vova can put a brick on parts 2 and 3 to make the wall $[2, 2, 2, 2, 5]$ and then put 3 bricks on parts 1 and 2 and 3 bricks on parts 3 and 4 to make it $[5, 5, 5, 5, 5]$.

In the second example Vova can put no bricks in the wall.

In the third example the wall is already complete.

Difficulty: HARD
Tags: Data structures

Implementation
Skill types: Data structures

Starter code:

Solutions:
def f():
	b = [a[0]]
	for e in a[1:]:
		if b != []:
			if e > b[-1]:
				print('NO')
				return
			elif e == b[-1]:
				b.pop()
			else:
				b.append(e)
		else:
			b.append(e)
	if len(b) == 0:
		print('YES')
	elif len(set(b)) == 1 and b[0] == max(a):
		print('YES')
	else:
		print('NO')
n = int(input())
a = [int(i) for i in input().split()]
f()


n = int(input())
a = [i for i in map(int, input().split(' '))]
mx = max(a)
stack = [a[0]]
q = True
for i in range(1, n):
	if len(stack) != 0:
		if a[i] == stack[-1]:
			stack.pop()
		elif a[i] > stack[-1]:
			q = False
			break
		else:
			stack.append(a[i])
	else:
		stack.append(a[i])
if len(stack) > 1 or (len(stack) == 1 and stack.pop() != mx):
	q = False
if q:
	print('YES')
else:
	print('NO')


n = int(input())
a = list(map(int, input().split()))
m = max(a)
b = []
for i in a:
	b.append(m - i)
st = [b[0]]
for i in range(1, n):
	if st and st[-1] == b[i]:
		st.pop()
	elif st and b[i] > st[-1]:
		st.append(b[i])
	elif st:
		print('NO')
		return
	else:
		st.append(b[i])
if len(st) == 0 or st[-1] == 0:
	print('YES')
else:
	print('NO')


n = int(input())
a = list(map(int, input().split()))
down = []
good = True
for guy in a:
	if len(down) == 0:
		down.append(guy)
	elif down[-1] > guy:
		down.append(guy)
	elif down[-1] == guy:
		down.pop()
	else:
		good = False
		break
if not good:
	print('NO')
elif len(down) > 1:
	print('NO')
elif len(down) == 1 and down[0] != max(a):
	print('NO')
else:
	print('YES')


(i, p) = (input, print)
(n, m, q) = (int(i()), 0, [])
f = q.append
for a in map(int, i().split()):
	if q:
		if a == q[-1]:
			q.pop()
		elif a > q[-1]:
			f(a)
			break
		else:
			f(a)
	else:
		f(a)
	m = max(m, a)
p('YES') if len(q) == 0 or (len(q) == 1 and q[0] == m) else p('NO')


import sys
sys.setrecursionlimit(3000)
n = int(input())
a = list(map(int, input().split()))
M = max(a)
m = min(a)
a = list([x - m for x in a])

def build(begin, target):
	stack = []
	nonlocal n, a
	i = begin
	currenth = a[begin]
	while i < n:
		while i + 1 < n and a[i + 1] == currenth:
			i += 1
		if i == n - 1:
			if not stack:
				return i
			elif (i - begin + 1) % 2 != 0 and a[i] != target:
				return -1
			else:
				(target, currenth, begin) = stack.pop()
		elif a[i + 1] > currenth:
			if (i - begin + 1) % 2 != 0:
				return -1
			elif a[i + 1] >= target:
				if not stack:
					return i
				else:
					(target, currenth, begin) = stack.pop()
			else:
				currenth = a[i + 1]
				i += 1
		else:
			stack.append((target, currenth, begin))
			i += 1
			target = currenth
			currenth = a[i]
			begin = i
res = build(0, M)
while res != -1 and res < n - 1:
	res = build(res + 1, M)
	print(res)
if res == n - 1:
	print('YES')
else:
	print('NO')


n = int(input())
a = [int(_) for _ in input().split()]
v = [a[0]]
max_v = 0
for i in range(1, n):
	max_v = max(max_v, a[i])
	if v and v[-1] == a[i]:
		v.pop()
		if v and v[-1] < a[i]:
			print('NO')
			exit()
	else:
		v.append(a[i])
print('NO' if len(v) > 1 or (v and v[0] < max_v) else 'YES')


i = int(input())
s = input().split()
m = max(list(map(int, s)))
l = []
for j in s:
	if not l or int(j) < l[-1]:
		l.append(int(j))
	elif int(j) == l[-1]:
		l.pop()
	else:
		print('NO')
		exit()
if len(l) == 1 and l[0] >= m or len(l) == 0:
	print('YES')
else:
	print('NO')


def main():
	n = int(input())
	m = 0
	stack = []
	for val in map(int, input().split()):
		if stack:
			if val == stack[-1]:
				stack.pop()
			elif val > stack[-1]:
				stack.append(val)
				break
			else:
				stack.append(val)
		else:
			stack.append(val)
		m = max(m, val)
	print('YES' if len(stack) == 0 or (len(stack) == 1 and stack[0] == m) else 'NO')
main()


import collections as c
(i, p) = (input, print)
(n, m, q) = (int(i()), 0, c.deque())
(f, l) = (q.append, len)
for a in map(int, i().split()):
	if q:
		if a == q[-1]:
			q.pop()
		elif a > q[-1]:
			f(a)
			break
		else:
			f(a)
	else:
		f(a)
	m = max(m, a)
if l(q) == 0 or (l(q) == 1 and q[0] == m):
	p('YES')
else:
	p('NO')


n = int(input())
a = list(map(int, input().split()))
b = [0] * 1000000
sp = -1
max = 0
f = True
for i in range(n):
	sp = sp + 1
	b[sp] = a[i]
	if b[sp] > max:
		max = b[sp]
	if sp > 0:
		if b[sp] > b[sp - 1]:
			f = False
		if b[sp] == b[sp - 1]:
			sp = sp - 2
if f == True:
	if sp == 0:
		if b[sp] >= max:
			print('YES')
		else:
			print('NO')
	elif sp < 0:
		print('YES')
	else:
		print('NO')
else:
	print('NO')


from collections import deque as d
(n, m, q) = (int(input()), 0, d())
for i in map(int, input().split()):
	if q:
		if i == q[-1]:
			q.pop()
		elif i > q[-1]:
			q.append(i)
			break
		else:
			q.append(i)
	else:
		q.append(i)
	m = max(m, i)
if len(q) == 0 or (len(q) == 1 and q[0] == m):
	print('YES')
else:
	print('NO')


def D2new():
	n = int(input())
	if n == 1:
		print('YES')
		return
	bricks = input().split()
	bricks = [int(x) for x in bricks]
	stack = []
	m = min(bricks)
	M = max(bricks)
	for i in range(n):
		if not len(stack):
			stack.append(bricks[i])
			continue
		if stack[-1] == bricks[i]:
			stack.pop()
			continue
		if stack[-1] == m:
			print('NO')
			return
		stack.append(bricks[i])
	if len(stack) == 0:
		print('YES')
		return
	if len(stack) == 1:
		print('YES') if stack[0] == M else print('NO')
		return
	print('NO')
D2new()


from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import combinations
import functools
import sys
import math
MAX = sys.maxsize
MAXN = 10 ** 6 + 10
MOD = 998244353

def isprime(n):
	n = abs(int(n))
	if n < 2:
		return False
	if n == 2:
		return True
	if not n & 1:
		return False
	for x in range(3, int(n ** 0.5) + 1, 2):
		if n % x == 0:
			return False
	return True

def mhd(a, b, x, y):
	return abs(a - x) + abs(b - y)

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

def charIN():
	return sys.stdin.readline().strip().split()
t = [(-1, -1)] * 1000010

def create(a):
	nonlocal t, n
	for i in range(n, 2 * n):
		t[i] = (a[i - n], i - n)
	for i in range(n - 1, 0, -1):
		x = [t[2 * i], t[2 * i + 1]]
		x.sort(key=lambda x: x[0])
		t[i] = x[1]

def update(idx, value):
	nonlocal t, n
	idx = idx + n
	t[idx] = value
	while idx > 1:
		idx = idx // 2
		x = [t[2 * idx], t[2 * idx + 1]]
		x.sort(key=lambda x: x[0])
		t[idx] = x[1]

def dis(a, b, k):
	ans = 0
	for i in range(k):
		ans += abs(a[i] - b[i])
	return ans

def cal(n, k):
	res = 1
	c = [0] * (k + 1)
	c[0] = 1
	for i in range(1, n + 1):
		for j in range(min(i, k), 0, -1):
			c[j] = (c[j] + c[j - 1]) % MOD
	return c[k]
n = int(input())
l = list(numIN())
x = []
for i in range(n):
	if x and x[-1] == l[i]:
		x.pop()
		continue
	if x and x[-1] < l[i]:
		print('NO')
		return
	x.append(l[i])
if x and x[-1] != max(l):
	print('NO')
else:
	print('YES')


n = int(input())
l = list(map(int, input().split()))
k = max(l)
s = []
i = 0
d = 0
while i < len(l):
	if len(s) == 0:
		s.append(l[i])
	elif s[-1] == l[i]:
		s.pop()
	elif s[-1] != l[i]:
		if s[-1] < l[i]:
			print('NO')
			d = 1
			break
		s.append(l[i])
	i += 1
if d == 0:
	if len(s) == 0 or (len(s) == 1 and s[0] == k):
		print('YES')
	else:
		print('NO')


n = int(input())
l = list(map(int, input().split()))
stack = []
h = l[0]
if n == 1:
	print('YES')
	exit(0)
for i in range(1, n):
	if len(stack) == 0 and l[i] > h:
		if i % 2 == 1:
			print('NO')
			exit(0)
	elif l[i] > h:
		lh = -1
		while len(stack) > 0 and stack[-1][0][0] <= l[i]:
			k = stack.pop()
			if (i - k[1]) % 2 == 1:
				print('NO')
				exit(0)
			if k[0][1] > l[i]:
				stack.append([[l[i] + 1, k[0][1]], k[1]])
				lh = l[i]
			else:
				lh = k[0][1]
		if lh != l[i] and i % 2 == 1:
			print('NO')
			exit(0)
	elif l[i] < h:
		stack.append([[l[i] + 1, h], i])
	h = l[i]
for i in stack:
	if (n - i[1]) % 2 == 1:
		print('NO')
		exit(0)
print('YES')


import sys

def rint():
	return map(int, sys.stdin.readline().split())
n = int(input())
a = list(rint())
stack = [a[0]]
for i in range(1, n):
	if len(stack) == 0:
		stack.append(a[i])
	elif a[i] > stack[-1]:
		stack.append(a[i])
		break
	elif a[i] == stack[-1]:
		stack.pop()
	else:
		stack.append(a[i])
if len(stack) > 1:
	print('NO')
elif len(stack) == 1:
	if max(a) == stack[0]:
		print('YES')
	else:
		print('NO')
else:
	print('YES')


import collections, atexit, math, sys, bisect
sys.setrecursionlimit(1000000)

def getIntList():
	return list(map(int, input().split()))
try:
	import numpy

	def dprint(*args, **kwargs):
		print(*args, file=sys.stderr)
	dprint('debug mode')
except Exception:

	def dprint(*args, **kwargs):
		pass
inId = 0
outId = 0
if inId > 0:
	dprint('use input', inId)
	sys.stdin = open('input' + str(inId) + '.txt', 'r')
if outId > 0:
	dprint('use output', outId)
	sys.stdout = open('stdout' + str(outId) + '.txt', 'w')
	atexit.register(lambda : sys.stdout.close())
(N,) = getIntList()
za = getIntList()
mh = max(za)
za.append(mh)
duo = [(mh, 0)]
for i in range(N + 1):
	h = za[i]
	while duo:
		if i % 2 != duo[-1][1] % 2:
			dprint(i)
			print('NO')
			return
		if h >= duo[-1][0]:
			lh = duo[-1][0]
			duo.pop()
			if h == lh:
				break
		else:
			break
	duo.append((h, i + 1))
print('YES')


n = int(input())
l = [int(x) for x in input().split()]
st = []
for i in l:
	d = i
	if len(st) and st[-1] == d:
		st.pop()
	elif len(st) == 0 or st[-1] > d:
		st.append(d)
	else:
		print('NO')
		break
else:
	if len(st) == 0 or (len(st) == 1 and st[-1] == max(l)):
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
A = list(map(int, input().split()))
AX = [(A[i], i) for i in range(n)]
QUE = deque()
for i in range(n):
	QUE.append(AX[i])
	while len(QUE) >= 2 and QUE[-1][0] == QUE[-2][0] and (A[QUE[-2][1]] >= A[QUE[-2][1] + 1]):
		QUE.pop()
		QUE.pop()
if len(QUE) >= 2:
	print('NO')
elif len(QUE) == 1:
	if QUE[0][0] == max(A):
		print('YES')
	else:
		print('NO')
else:
	print('YES')


from __future__ import division, print_function
import cmath
import itertools
import math
import operator as op
import sys
from atexit import register
from bisect import bisect_left, bisect_right
from collections import deque
if sys.version_info[0] < 3:
	from io import BytesIO as stream
else:
	from io import StringIO as stream
	from math import gcd
if sys.version_info[0] < 3:

	class dict(dict):

		def items(self):
			return dict.iteritems(self)

		def keys(self):
			return dict.iterkeys(self)

		def values(self):
			return dict.itervalues(self)

	def gcd(x, y):
		while y:
			(x, y) = (y, x % y)
		return x
	input = raw_input
	range = xrange
	filter = itertools.ifilter
	map = itertools.imap
	zip = itertools.izip

def sync_with_stdio(sync=True):
	global input, flush
	if sync:
		flush = sys.stdout.flush
	else:
		sys.stdin = stream(sys.stdin.read())
		input = lambda : sys.stdin.readline().rstrip('\r\n')
		sys.stdout = stream()
		register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))

def main():
	n = int(input())
	a = list(map(int, input().split(' ')))
	m = max(a)
	q = deque()
	for ai in a:
		if q:
			if ai == q[-1]:
				q.pop()
			elif ai > q[-1]:
				q.append(ai)
				break
			else:
				q.append(ai)
		else:
			q.append(ai)
	if len(q) == 0 or (len(q) == 1 and q[0] == m):
		print('YES')
	else:
		print('NO')
sync_with_stdio(False)
main()


n = int(input())
b = -1
a = input().split()
(l, r) = ([], True)
for i in a:
	tmp = int(i)
	b = max(b, tmp)
	if l == [] or l[-1] > tmp:
		l.append(tmp)
	elif l[-1] == tmp:
		l.pop()
	else:
		r = False
		break
print('YES' if r and (len(l) == 0 or (len(l) == 1 and l[0] >= b)) else 'NO')


n = int(input())
a = list(map(int, input().split()))
l = []
val = -1
for i in a:
	if l == [] or l[-1] != i:
		l.append(i)
	else:
		val = l.pop()
		if l:
			if val > l[-1]:
				print('NO')
				exit()
if l:
	if len(l) > 1:
		print('NO')
	elif max(a) != l[-1]:
		print('NO')
	else:
		print('YES')
else:
	print('YES')


n = int(input())
MX = 2 * 1000 * 1000 * 1000
l = list(map(int, input().split()))
right = [-1 for i in range(n)]
left = [-1 for i in range(n)]
stk = []
for (i, v) in enumerate(l):
	if len(stk) == 0 or v <= stk[-1][0]:
		stk.append((v, i))
	else:
		while len(stk) > 0 and stk[-1][0] < v:
			x = stk.pop()
			right[x[1]] = i
		stk.append((v, i))
while len(stk) > 0:
	x = stk.pop()
	right[x[1]] = n
for i in range(n - 1, -1, -1):
	v = l[i]
	if len(stk) == 0 or v <= stk[-1][0]:
		stk.append((v, i))
	else:
		while len(stk) > 0 and stk[-1][0] < v:
			x = stk.pop()
			left[x[1]] = i
		stk.append((v, i))
flag = True
for (x, y) in zip(left, right):
	if y - x > n or (y - x) % 2 == 1:
		continue
	else:
		flag = False
		break
print('YES' if flag else 'NO')


n = int(input())
a = list(map(int, input().split()))
k = max(a)
f = -1
q = 10 ** 6 * [-1]
pnt = -1
ans = 'YES'
for i in range(n):
	if pnt == -1:
		pnt += 1
		q[pnt] = a[i]
		f = i
	elif q[pnt] == a[i]:
		q[pnt] = -1
		pnt -= 1
	elif q[pnt] < a[i]:
		ans = 'NO'
	else:
		pnt += 1
		q[pnt] = a[i]
		f = i
if pnt == 0:
	if q[0] != k:
		ans = 'NO'
if pnt > 0 or (f == n - 1 and a[-1] != k):
	ans = 'NO'
print(ans)


n = int(input())
a = list(map(int, input().split()))
s = []
flag = 1
for i in range(0, n):
	if len(s) and s[-1] == a[i]:
		s.pop()
	elif len(s) == 0 or s[-1] > a[i]:
		s.append(a[i])
	else:
		print('NO')
		flag = 0
		break
if flag == 1:
	if len(s) == 0 or (len(s) == 1 and s[-1] == max(a)):
		print('YES')
	else:
		print('NO')


from sys import stdin

def myfunction(n, arr):
	mystack = []
	mystack.append(arr[0])
	max_el = max(arr)
	for i in range(1, n):
		if len(mystack) > 0:
			if mystack[-1] - arr[i] == 0:
				mystack.pop()
			elif mystack[-1] > arr[i]:
				mystack.append(arr[i])
			else:
				return 'NO'
		else:
			mystack.append(arr[i])
	if len(mystack) <= 1:
		if len(mystack) == 1:
			if mystack[-1] == max_el:
				return 'YES'
			else:
				return 'NO'
		return 'YES'
	else:
		return 'NO'
n = int(stdin.readline().strip())
arr = list(map(int, stdin.readline().split()))
print(myfunction(n, arr))


n = int(input())
a = list(map(int, input().split()))
b = [[a[0], 1]]
fl = False
for i in range(1, n):
	if fl:
		break
	if a[i] == b[-1][0]:
		b[-1][1] += 1
	elif a[i] < b[-1][0]:
		b.append([a[i], 1])
	else:
		while len(b) != 0 and a[i] > b[-1][0]:
			if b[-1][1] % 2 != 0:
				print('NO')
				fl = True
				break
			b.pop()
		if len(b) == 0 or a[i] < b[-1][0]:
			b.append([a[i], 1])
		else:
			b[-1][1] += 1
if not fl:
	i = len(b) - 1
	while i != 0:
		if b[i][1] % 2 != 0:
			fl = True
			break
		i -= 1
	if fl:
		print('NO')
	else:
		print('YES')


import sys
n = int(sys.stdin.readline())
cur_str = sys.stdin.readline().strip().split()
array = [int(elem) for elem in cur_str]
i = 0
stack = []
ans = True
maximum = -1
while i < len(array):
	maximum = max(maximum, array[i])
	if not stack or array[i] < stack[-1]:
		stack.append(array[i])
	elif stack[-1] < array[i]:
		ans = False
		break
	elif stack[-1] == array[i]:
		stack.pop()
	i += 1
for i in range(1, len(stack)):
	if stack[i] != stack[i - 1]:
		ans = False
		break
if stack and min(stack) < maximum:
	ans = False
if ans == True or n == 1:
	print('YES')
else:
	print('NO')