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 horizontally on the neighboring 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).

The next paragraph is specific to the version 1 of the problem.

Vova can also put bricks vertically. That means increasing height of any part of the wall by 2.

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
YES

Input
2
10 10

Output
YES

Input
3
1 2 3

Output
NO



-----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 a brick vertically on part 3 to make the wall $[4, 5, 5]$, then horizontally on parts 2 and 3 to make it $[4, 6, 6]$ and then vertically on part 1 to make it $[6, 6, 6]$.

In the third example the wall is already complete.

Difficulty: HARD
Tags: Mathematics

Implementation

Greedy algorithms
Skill types: Greedy algorithms
Expected Time Complexity: O(N)

Starter code:

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


n = int(input())
a = list(map(int, input().split()))
(n0, n1) = (0, 0)
for (i, x) in enumerate(a):
	add = (x + 1) // 2
	if i % 2 == 0:
		n0 += add
		n1 += x - add
	else:
		n1 += add
		n0 += x - add
if n0 - n1 == 0 or (n0 - n1 == 1 and len(a) % 2 == 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, p) = (input, print)
(n, b, q) = (int(i()), [int(x) & 1 for x in i().split()], [])
f = q.append
f(b[0])
for a in b[1:]:
	q.pop() if q and q[-1] == a else f(a)
p('NO' if len(q) > 1 else 'YES')


n = int(input())
a = [int(i) for i in input().split()]
st = []
for i in a:
	if len(st) > 0 and st[-1] == i & 1:
		st.pop()
	else:
		st.append(i & 1)
if len(st) <= 1:
	print('YES')
else:
	print('NO')


while True:
	try:
		n = int(input())
		nu = [int(x) for x in input().split()]
		re = list(map(lambda x: (x + 1) % 2, nu))
		posi = False
		su = 0
		ba = 0
		for i in range(0, n - 1, 2):
			if re[i] == re[i + 1]:
				pass
			elif re[i] == 0:
				su += 1
			else:
				ba += 1
		posi = su == ba
		if n % 2 == 1:
			if su + 1 == ba and re[n - 1] == 0:
				posi = True
			if ba + 1 == su and re[n - 1] == 1:
				posi = True
		if not posi:
			print('NO')
		else:
			print('YES')
	except Exception as e:
		break


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


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


n = int(input())
a = list(map(int, input().split()))
for i in range(n):
	a[i] &= 1
b = list(a)
for i in range(n):
	b[i] = a[i] ^ 1

def check(a):
	n = len(a)
	(s1, s2) = (0, 0)
	for i in range(n):
		if i & 1 == 0:
			s1 += a[i]
		else:
			s2 += a[i]
	diff = abs(s1 - s2)
	if diff % 3 == 0:
		return True
	return False
possible = check(a) or check(b)
if possible:
	print('YES')
else:
	print('NO')


n = int(input())
l1 = list(map(int, input().split()))
segments = 0
for i in range(0, n):
	if l1[i] % 2 == 1:
		if i % 2 == 1:
			segments -= 1
		else:
			segments += 1
if n % 2 == 1 and (segments == 0 or segments == 1):
	print('YES')
elif n % 2 == 0 and segments == 0:
	print('YES')
else:
	print('NO')


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


n = int(input())
aa = []
l = [*map(int, input().split())]
for i in l:
	res = i % 2
	if not len(aa) or aa[-1] != res:
		aa.append(res)
	else:
		aa.pop(-1)
print('YES' if len(aa) <= 1 else 'NO')


n = int(input())
arr = list(map(int, input().split()))
arr = list(map(lambda x: x % 2, arr))
stack = []
for i in range(n):
	if len(stack):
		if stack[-1] == arr[i]:
			stack.pop()
		else:
			stack.append(arr[i])
	else:
		stack.append(arr[i])
if len(stack) == 0 or len(stack) == 1:
	print('YES')
else:
	print('NO')


n = int(input())
a = list(map(int, input().split()))
s = []
for i in range(n):
	a[i] = a[i] & 1
for i in range(n):
	if len(s) == 0 or s[-1] != a[i]:
		s.append(a[i])
	else:
		s.pop()
if len(s) <= 1:
	print('YES')
else:
	print('NO')


def D1():
	n = int(input())
	bricks = input().split()
	bricks = [int(x) % 2 for x in bricks]
	stack = []
	for i in range(n):
		if not len(stack):
			stack.append(bricks[i])
			continue
		if stack[-1] == bricks[i]:
			stack.pop()
			continue
		stack.append(bricks[i])
	if len(stack) < 2:
		print('YES')
		return
	print('NO')
D1()


(a, n) = ([], input())
for i in [int(x) & 1 for x in input().split()]:
	if a and a[-1] == i:
		a.pop()
	else:
		a.append(i)
print(len(a) > 1 and 'NO' or 'YES')


n = int(input())
a = list(map(int, input().split()))
c = 0
for i in range(n):
	if a[i] % 2 == 1:
		if i % 2 == 1:
			c = c - 1
		else:
			c = c + 1
if n % 2 == 1 and (c == 0 or c == 1) or (n % 2 == 0 and c == 0):
	print('YES')
else:
	print('NO')


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


x = int(input())
l = list(map(int, input().split()))
l1 = []
for i in range(x):
	if l1 != [] and l[i] % 2 == l1[-1]:
		del l1[-1]
	else:
		l1 += [l[i] % 2]
if len(l1) <= 1:
	print('YES')
else:
	print('NO')


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()))
st = [a[0]]
for i in range(1, n):
	if len(st) > 0 and st[-1] % 2 == a[i] % 2:
		st.pop()
	else:
		st.append(a[i])
if len(st) <= 1:
	print('YES')
else:
	print('NO')


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


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 map(int, sys.stdin.readline().strip().split())

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

def create(a):
	global 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):
	global 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')
		exit(0)
	x.append(l[i])
if x and x[-1] != max(l):
	print('NO')
else:
	print('YES')


def wall(n, a):
	a = [0 if x % 2 == 0 else 1 for x in a]
	stack = [a[0]]
	append = stack.append
	pop = stack.pop
	for i in range(1, n):
		if len(stack) > 0:
			ele = stack[-1]
			if ele == a[i]:
				pop()
			else:
				append(a[i])
		else:
			append(a[i])
	return len(stack) <= 1
n = int(input())
a = map(int, input().split())
res = wall(n, a)
print('YES' if res else 'NO')


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


n = int(input())
l = [int(x) for x in input().split()]
st = []
for i in l:
	d = i % 2
	if len(st) and st[-1] == d:
		st.pop()
	else:
		st.append(d)
if len(st) < 2:
	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()


n = int(input())
inp = input()
alt = list(map(int, inp.rstrip().split()))
nuovo = []
for i in range(n):
	alt[i] %= 2
	if len(nuovo) != 0:
		if nuovo[-1] == alt[i]:
			nuovo.pop()
		else:
			nuovo.append(alt[i])
	else:
		nuovo.append(alt[i])
if len(nuovo) > 1:
	print('NO')
else:
	print('YES')


n = int(input())
l = []
for i in list(map(int, input().split())):
	tmp = 1 & i
	if l == [] or l[-1] != tmp:
		l.append(tmp)
	else:
		l.pop()
print('YES' if len(l) <= 1 else 'NO')


n = int(input())
a = [i for i in map(int, input().split(' '))]
mx = max(a)
stack = [a[0]]
for i in range(1, n):
	if len(stack) != 0:
		if a[i] % 2 == stack[-1] % 2:
			stack.pop()
		else:
			stack.append(a[i])
	else:
		stack.append(a[i])
if len(stack) > 1:
	print('NO')
else:
	print('YES')


n = int(input())
l = list(map(int, input().split()))
track = []
track.append(l[0] % 2)
r = ''
for i in range(1, n):
	if track == [] or track[-1] != l[i] % 2:
		track.append(l[i] % 2)
	else:
		track.pop()
if len(track) <= 1:
	r = 'YES'
else:
	r = 'NO'
print(r)


def merge(b1, b2):
	if abs(b1[0] - b2[0]) % 2 == 0 or (b1[1] % 2 == 0 and b2[1] % 2 == 0):
		return (True, (max(b1[0], b2[0]), b1[1] + b2[1]))
	elif b1[1] % 2 == 0 or b2[1] % 2 == 0:
		if b1[1] % 2 == 1:
			return (True, (b1[0] if b1[0] > b2[0] else b2[0] + 1, b1[1] + b2[1]))
		if b2[1] % 2 == 1:
			return (True, (b2[0] if b2[0] > b1[0] else b1[0] + 1, b1[1] + b2[1]))
	return (False, None)
n = int(input())
x = [int(i) for i in input().split()]
wl = [[x[0], 1]]
for i in x[1:]:
	if i == wl[-1][0]:
		wl[-1][1] += 1
	else:
		wl.append([i, 1])
i = 1
last_brick = wl[0]
res = []

def fix_res():
	global res, last_brick
	if len(res) == 0:
		return
	x = merge(res[-1], last_brick)
	while x[0]:
		res.pop()
		last_brick = x[1]
		x = merge(res[-1], last_brick) if len(res) != 0 else (False,)
for i in wl[1:]:
	fix_res()
	x = merge(last_brick, i)
	if x[0] == False:
		res.append(last_brick)
		last_brick = i
	else:
		last_brick = x[1]
fix_res()
res.append(last_brick)
res = len(res) == 1
print('YES' if res else 'NO')


class node:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def is_solvable(this):
	while this.pre is not None or this.next is not None:
		if this.pre is not None:
			if this.val[0] % 2 == 0:
				merged = node((this.pre.val[0] % 2, this.pre.val[1]))
				merged.next = this.next
				merged.pre = this.pre.pre
				if this.next is not None:
					this.next.pre = merged
				if this.pre.pre is not None:
					this.pre.pre.next = merged
				this = merged
				continue
			elif this.pre.val[0] % 2 == 0:
				merged = node((this.val[0] % 2, this.val[1]))
				merged.next = this.next
				merged.pre = this.pre.pre
				if this.next is not None:
					this.next.pre = merged
				if this.pre.pre is not None:
					this.pre.pre.next = merged
				this = merged
				continue
			elif not this.val[1] ^ this.pre.val[1]:
				merged = node((this.val[0] % 2 + this.pre.val[0] % 2, this.val[1]))
				merged.next = this.next
				merged.pre = this.pre.pre
				if this.next is not None:
					this.next.pre = merged
				if this.pre.pre is not None:
					this.pre.pre.next = merged
				this = merged
				continue
		if this.next is not None:
			if this.val[0] % 2 == 0:
				merged = node((this.next.val[0] % 2, this.next.val[1]))
				merged.next = this.next.next
				merged.pre = this.pre
				if this.next.next is not None:
					this.next.next.pre = merged
				if this.pre is not None:
					this.pre.next = merged
				this = merged
				continue
			elif this.next.val[0] % 2 == 0:
				merged = node((this.val[0] % 2, this.val[1]))
				merged.next = this.next.next
				merged.pre = this.pre
				if this.next.next is not None:
					this.next.next.pre = merged
				if this.pre is not None:
					this.pre.next = merged
				this = merged
				continue
			elif not this.val[1] ^ this.next.val[1]:
				merged = node((this.val[0] % 2 + this.next.val[0] % 2, this.val[1]))
				merged.next = this.next.next
				merged.pre = this.pre
				if this.next.next is not None:
					this.next.next.pre = merged
				if this.pre is not None:
					this.pre.next = merged
				this = merged
				continue
			this = this.next
		else:
			return False
	return True

def great_vova_wall(size, wall):
	count = 1
	state = wall[0] % 2 == 0
	head = None
	this = head
	for i in range(1, size):
		if state ^ wall[i] % 2 == 0:
			new = node((count, state))
			if this is not None:
				new.pre = this
				this.next = new
			if head is None:
				head = new
			count = 1
			state = wall[i] % 2 == 0
			this = new
		else:
			count += 1
	new = node((count, state))
	if this is not None:
		new.pre = this
		this.next = new
	if head is None:
		head = new
	return is_solvable(head)
n = int(input())
a = list(map(int, input().split()))
if great_vova_wall(n, a):
	print('YES')
else:
	print('NO')


def f():
	b = [a[0]]
	for e in a[1:]:
		if b != []:
			if e == b[-1] or abs(e - b[-1]) % 2 == 0:
				b.pop()
			else:
				b.append(e)
		else:
			b.append(e)
	for i in range(1, len(b)):
		if abs(b[i] - b[i - 1]) % 2:
			print('NO')
			return
	print('YES')
n = int(input())
a = [int(i) for i in input().split()]
f()


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


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


import sys
sys.setrecursionlimit(3000)
n = int(input())
a = list(map(int, input().split()))
M = max(a)
m = min(a)
a = list(map(lambda x: x - m, a))

def build(begin, target):
	stack = []
	global 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:
				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)
if res == n - 1:
	print('YES')
else:
	print('NO')


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())
arr = list(map(int, input().split()))
stack = []
for i in range(n):
	if len(stack) <= 1:
		stack.append(arr[i] % 2)
		continue
	else:
		while len(stack) >= 2 and stack[-1] == stack[-2]:
			stack.pop()
			stack.pop()
		stack.append(arr[i] % 2)
while len(stack) >= 2 and stack[-1] == stack[-2]:
	stack.pop()
	stack.pop()
if len(stack) <= 1:
	print('YES')
else:
	print('NO')


(i, p, l) = (input, print, len)
(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 l(q) == 0 or (l(q) == 1 and q[0] == m) else p('NO')


n_input = int(input())
l_input = list(map(int, str(input()).split()))
l_binary = []
for _ in range(n_input):
	pop = l_input.pop() % 2
	if l_binary == []:
		l_binary.append(pop)
	elif pop == l_binary[-1]:
		l_binary.pop()
	else:
		l_binary.append(pop)
n = len(l_binary)
if n <= 1:
	print('YES')
else:
	print('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())
bricks = list(map(int, input().split()))

def solve(n, bricks):
	if n <= 1:
		return 'YES'
	(x, MAX) = (list(), float('-inf'))
	for b in bricks:
		if not x or x[-1] > b:
			x.append(b)
		elif x[-1] == b:
			MAX = max(b, MAX)
			x.pop()
		else:
			return 'No'
	return 'YES' if len(x) == 0 or (len(x) == 1 and x[0] >= MAX) else 'NO'
print(solve(n, bricks))


i = int(input())
s = input().split()
l = []
for j in s:
	if not l or int(j) % 2 != l[-1]:
		l.append(int(j) % 2)
	else:
		l.pop()
if len(l) < 2:
	print('YES')
else:
	print('NO')


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


n = int(input())
L = [int(x) % 2 for x in input().split()]
S = []
temp = 1
LW = []
RW = []
Close = []
for i in range(1, n):
	if L[i] == L[i - 1]:
		temp += 1
	else:
		S.append(temp)
		temp = 1
S.append(temp)
z = 0
for i in range(0, len(S)):
	S[i] = S[i] % 2
	if S[i] == 0:
		z += 1
		LW.append(i)
		RW.append(len(S) - i - 1)
		if len(LW) > 1:
			Close.append(LW[-1] - LW[-2])
index = 0
removed = 0
while index < z - 1:
	if Close[index] <= LW[index] - removed:
		removed += 2 * Close[index]
		index += 2
	else:
		removed += 2 * (LW[index] - removed) + 1
		index += 1
if index == z - 1:
	if abs(LW[z - 1] - removed - RW[z - 1]) <= 1:
		print('YES')
	else:
		print('NO')
elif removed >= len(S) - 1:
	print('YES')
else:
	print('NO')


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

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

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def solve(case):
	n = int(inp())
	a = lis()
	mx = max(a)
	for i in range(n):
		if (mx - a[i]) % 2 == 0:
			a[i] = mx
		else:
			a[i] = mx + 1
	for i in range(n - 1):
		if a[i] == mx:
			if a[i + 1] == mx:
				a[i] = mx + 1
				a[i + 1] = mx + 1
	if a.count(mx) == 0:
		print('YES')
		return
	cnt = 0
	have = []
	for i in range(0, n):
		if len(have) == 0:
			have.append(a[i])
			continue
		if have[len(have) - 1] == a[i]:
			have.pop()
		else:
			have.append(a[i])
	if len(have) < 2:
		print('YES')
	else:
		print('NO')
testcase(1)


n = int(input())
re = [int(x) % 2 for x in input().split()]
su = 0
ba = 0
for i in range(0, n - 1, 2):
	if re[i] == re[i + 1]:
		pass
	elif re[i] == 0:
		su += 1
	else:
		ba += 1
posi = su == ba
if n % 2 == 1:
	if su + 1 == ba and re[n - 1] == 0:
		posi = True
	if ba + 1 == su and re[n - 1] == 1:
		posi = True
if not posi:
	print('NO')
else:
	print('YES')


import math
n = int(input())
columns = list(map(int, input().rstrip().split()))
modcolumns = [i % 2 for i in columns]
test = 0
previouslist = []
for i in range(0, n):
	if len(previouslist) == 0:
		previouslist.append(modcolumns[i])
	elif modcolumns[i] == previouslist[-1]:
		previouslist.pop()
	else:
		previouslist.append(modcolumns[i])
if len(previouslist) <= 1:
	print('YES')
else:
	print('NO')


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


import sys
import collections as cc
I = lambda : list(map(int, input().split()))
(n,) = I()
l = I()
for i in range(n):
	l[i] &= 1
st = [l[0]]
i = 1
for i in range(1, n):
	if st and st[-1] == l[i]:
		st.pop()
	else:
		st.append(l[i])
if len(st) <= 1:
	f = 0
else:
	f = 1
print('YNEOS'[f::2])


from sys import stdin

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


import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
n = int(input())
A = list(map(int, input().split()))
A2 = [A[i] % 2 for i in range(n)]
if n == 1:
	print('YES')
	sys.exit()
if n == 2:
	if A2[0] != A2[1]:
		print('NO')
		sys.exit()
	else:
		print('YES')
		sys.exit()
i = 0
j = 1
SKIPLIST = [0] * n
BLIST = [None] * (n + 1)

def back(i):
	if i == -1:
		return -1
	if SKIPLIST[i] == 0:
		return i
	if BLIST[i] != None:
		BLIST[i] = back(BLIST[i])
		return BLIST[i]
	else:
		BLIST[i] = back(i - 1)
		return BLIST[i]
while j < n:
	if A2[i] != A2[j]:
		(i, j) = (j, j + 1)
	else:
		SKIPLIST[i] = SKIPLIST[j] = 1
		i = back(i)
		if i == -1:
			(i, j) = (j + 1, j + 2)
		else:
			j = j + 1
if SKIPLIST.count(0) <= 1:
	print('YES')
else:
	print('NO')


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
I = lambda : list(map(int, input().split()))
(n,) = I()
l = I()
an = [l[0] % 2]
for i in range(1, n):
	if an and l[i] % 2 == an[-1] % 2:
		an.pop()
	else:
		an.append(l[i] % 2)
if not an:
	an = [1]
print('YNEOS'[bool(len(an) - 1)::2])


import collections as c
(i, p, l, j) = (input, print, len, int)
(n, m, q) = (j(i()), 0, c.deque())
f = q.append
for a in map(j, 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 l(q) == 0 or (l(q) == 1 and q[0] == m) else p('NO')


n = int(input())
a = [int(x) for x in input().split()]
s = []
mx = 0
for x in a:
	mx = max(mx, x)
	if len(s) == 0:
		s.append(x)
	elif s[len(s) - 1] > x:
		s.append(x)
	elif s[len(s) - 1] == x:
		s.pop()
	else:
		print('NO')
		quit()
while len(s) > 0 and s[len(s) - 1] == mx:
	s.pop()
if len(s) == 0:
	print('YES')
else:
	print('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())
a = [int(x[-1]) % 2 for x in input().split()]
i = 0
series = a[0]
series_len = 0
res = []
prev = ''
while i <= n:
	if i < n and a[i] == series:
		series_len += 1
	else:
		if series_len % 2 != 0:
			if prev == series:
				res.pop(-1)
				prev = res[-1] if len(res) >= 1 else ''
			else:
				res.append(series)
				prev = series
		if i < n:
			series = a[i]
		series_len = 1
	i += 1
print('Yes') if len(res) <= 1 else print('No')


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


import math
n = int(input())
a = list(map(int, input().split()))
b = [2]
for i in a:
	y = b.pop()
	if i % 2 == y:
		continue
	else:
		b.append(y)
		b.append(i % 2)
if len(b) > 2:
	print('NO')
else:
	print('YES')


import sys
input = sys.stdin.readline
from collections import *
n = int(input())
a = list(map(int, input().split()))
q = deque([])
for i in range(n):
	if len(q) > 0 and q[-1] % 2 == a[i] % 2:
		q.pop()
	else:
		q.append(a[i])
if len(q) <= 1:
	print('YES')
else:
	print('NO')


n = int(input())
wall = list(map(int, input().split()))
if n == 1:
	print('YES')
else:
	in1 = []
	for i in range(n):
		wall[i] = wall[i] % 2
		if wall[i] == 1:
			in1.append(i)
	if len(in1) == 0 or len(in1) == n:
		print('YES')
	elif len(in1) == 1:
		if (n - 1) % 2 == 0 and in1[0] % 2 == 0 and ((n - in1[0] - 1) % 2 == 0):
			print('YES')
		else:
			print('NO')
	else:
		i = 0
		while i + 1 < len(in1):
			if i >= 0 and i + 1 < len(in1) and ((in1[i + 1] - in1[i] - 1) % 2 == 0):
				del in1[i + 1]
				del in1[i]
				i -= 1
			else:
				i += 1
		if len(in1) == 0:
			print('YES')
		elif len(in1) == 1:
			if (n - 1) % 2 == 0 and in1[0] % 2 == 0 and ((n - in1[0] - 1) % 2 == 0):
				print('YES')
			else:
				print('NO')
		else:
			print('NO')


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()))
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 = 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')


n = int(input())
w = list(map(int, input().split()))
count = 0
for i in range(n):
	if w[i] % 2 == 1:
		if i % 2 == 1:
			count -= 1
		else:
			count += 1
if n % 2 == 1 and (count == 1 or count == 0):
	print('YES')
elif n % 2 == 0 and count == 0:
	print('YES')
else:
	print('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')


s = []
n = int(input())
a = list(map(lambda x: int(x) % 2, input().split()))
for i in a:
	if len(s) != 0 and s[-1] == i:
		s.pop()
	else:
		s.append(i)
if len(s) > 1:
	print('NO')
else:
	print('YES')


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:
		exit(print('NO'))
	else:
		st.append(b[i])
if len(st) == 0 or st[-1] == 0:
	print('YES')
else:
	print('NO')


n = int(input())
wl = list(map(int, input().split()))
stack = []
(a, t) = (0, wl[0])
for i in range(n + 1):
	if i < n and wl[i] == t:
		a += 1
	else:
		if len(stack) == 0:
			stack.append([t, a])
		elif a % 2 == 0 and t <= stack[-1][0]:
			pass
		elif t == stack[-1][0] and (stack[-1][1] + a) % 2 == 0:
			if len(stack) > 1 and stack[-1][0] <= stack[-2][0]:
				stack.pop()
			else:
				stack[-1][1] += a
		elif stack[-1][1] % 2 == 0 and stack[-1][0] <= t:
			stack.pop()
			stack.append([t, a])
		else:
			stack.append([t, a])
		if i < n:
			(a, t) = (1, wl[i])
if len(stack) < 2:
	print('YES', end='')
else:
	print('NO', end='')


n = int(input())
a = [int(x) % 2 for x in input().split()]
s = []
for x in a:
	if len(s) == 0:
		s.append(x)
	elif s[len(s) - 1] != x:
		s.append(x)
	else:
		s.pop()
if len(s) <= 1:
	print('YES')
else:
	print('NO')


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	y = 0
	a = list(map(int, input().split()))
	for v in a:
		if (v - y) % 2 == 1:
			y -= 1
		elif y < 0:
			y += 1
	if y == 0:
		print('YES')
		return
	y = 1
	for v in a:
		if (v - y) % 2 == 1:
			y -= 1
		elif y < 1:
			y += 1
	if y == 1:
		print('YES')
		return
	print('NO')
solve()


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


n = int(input())
a = [int(x[-1]) % 2 for x in input().split()]

def rule(s1, s2):
	if s1 == s2:
		return 'T'
	else:
		return False
i = 0
series = a[0]
series_len = 0
res = []
prev = ''
while i <= n:
	if i < n and a[i] == series:
		series_len += 1
	else:
		if series_len % 2 != 0:
			if series == 0:
				if prev == 'F0':
					res.pop(-1)
					if len(res) >= 1:
						prev = res[-1]
					else:
						prev = ''
				else:
					res.append('F0')
					prev = 'F0'
			elif prev == 'F1':
				res.pop(-1)
				if len(res) >= 1:
					prev = res[-1]
				else:
					prev = ''
			else:
				res.append('F1')
				prev = 'F1'
		if i < n:
			series = a[i]
			series_len = 1
	i += 1
if len(res) <= 1:
	print('Yes')
else:
	print('No')


n = int(input())
a = list(map(int, input().split()))
stack = []
for i in a:
	if stack and i & 1 == stack[-1]:
		stack.pop()
	else:
		stack.append(i & 1)
if len(stack) > 1:
	print('NO')
else:
	print('YES')


n = int(input())
a = map(lambda s: int(s) & 1, input().split())
st = []
for x in a:
	if len(st) > 0 and st[-1] == x:
		st.pop()
	else:
		st.append(x)
if len(st) <= 1:
	print('YES')
else:
	print('NO')


n = int(input())
a = list(map(int, input().split()))
b = 0
for i in range(n):
	if a[i] % 2 == 1:
		if i % 2 == 0:
			b += 1
		else:
			b -= 1
if n % 2 == 0:
	if b == 0:
		print('YES')
	else:
		print('NO')
elif b == 0 or b == 1:
	print('YES')
else:
	print('NO')


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')
			sys.exit()
		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())
A = list(map(int, input().split()))
s = []
for a in A:
	if s:
		if s[-1] % 2 == a % 2:
			s.pop()
		else:
			s.append(a)
	else:
		s.append(a)
if len(s) > 1:
	print('NO')
else:
	print('YES')


def main():
	n = int(input())
	a = list(map(int, input().split()))
	stack = []
	for val in a:
		if stack:
			last = stack.pop()
			if val % 2 != last % 2:
				stack.append(last)
				stack.append(val)
			else:
				pass
		else:
			stack.append(val)
	print('YES' if len(stack) <= 1 else 'NO')
main()


n = int(input())
bricks = list(map(int, input().split()))

def solve(n, bs):
	if n <= 1:
		return 'YES'
	x = list()
	for b in bs:
		if not x:
			x.append(b % 2)
			continue
		cur = x.pop()
		if cur == b % 2:
			continue
		else:
			x.append(cur)
			x.append(b % 2)
	return 'NO' if len(x) > 1 else 'YES'
print(solve(n, bricks))


n = int(input())
A = [int(x) % 2 == 0 for x in input().split(' ')]
segments = []
segmentLength = 1
for i in range(n):
	if i == n - 1:
		segments.append(segmentLength)
	elif A[i] == A[i + 1]:
		segmentLength += 1
	else:
		segments.append(segmentLength)
		segmentLength = 1
lastIndexStack = []
for i in range(len(segments)):
	if segments[i] != 0:
		if segments[i] % 2 == 0:
			if i == len(segments) - 1:
				for _ in range(len(lastIndexStack)):
					lastIndex = lastIndexStack.pop()
					segments[i] += segments[lastIndex]
					segments[lastIndex] = 0
					if segments[i] % 2 != 0:
						break
			else:
				j = 0
				while True:
					for _ in range(len(lastIndexStack)):
						lastIndex = lastIndexStack.pop()
						segments[i] += segments[lastIndex] + segments[i + 1 + j]
						segments[lastIndex] = 0
						segments[i + 1 + j] = 0
						j += 1
						if segments[i] % 2 != 0 or i + 1 + j > len(segments) - 1:
							break
					if segments[i] % 2 != 0 or i + 1 + j > len(segments) - 1:
						break
					segments[i] += segments[i + 1 + j]
					segments[i + 1 + j] = 0
					j += 1
					if segments[i] % 2 != 0 or i + 1 + j > len(segments) - 1:
						break
		if segments[i] != 0:
			lastIndexStack.append(i)
segments = [x for x in segments if x != 0]
if len(segments) == 1:
	print('YES')
else:
	print('NO')


n_input = int(input())
l_input = list(map(int, str(input()).split()))
l_binary = []
for _ in range(n_input):
	pop = l_input.pop() % 2
	if l_binary == []:
		l_binary.append(pop)
	elif pop == l_binary[-1]:
		l_binary.pop()
	else:
		l_binary.append(pop)

def solve(n, l_binary):
	if n <= 1:
		return 1
	elif n == 2:
		sum_l = sum(l_binary) % 2
		return sum_l - 1
	else:
		for k in range(n - 2):
			l_sequence = [l_binary[k], l_binary[k + 1], l_binary[k + 2]]
			if l_sequence == [0, 1, 0] or l_sequence == [1, 0, 1]:
				return 0
		return 1
if solve(len(l_binary), l_binary):
	print('YES')
else:
	print('NO')


import sys

def rint():
	return map(int, sys.stdin.readline().split())
h = 0
l = 1
n = int(input())
a = rint()
a = [i % 2 for i in a]
cnt = 0
cur = -1
ae = []
for i in range(n):
	if a[i] == 0:
		if cur == 0 or cur == -1:
			cur = 0
			cnt += 1
		else:
			ae.append([cur, cnt % 2])
			cnt = 1
			cur = 0
	elif cur == 1 or cur == -1:
		cur = 1
		cnt += 1
	else:
		ae.append([cur, cnt % 2])
		cnt = 1
		cur = 1
ae.append([cur, cnt % 2])
stack = []
for e in ae:
	if e[l] == 1:
		if len(stack) == 0:
			stack.append(e[h])
		elif e[h] == stack[-1]:
			stack.pop()
		else:
			stack.append(e[h])
if len(stack) > 1:
	print('NO')
else:
	print('YES')


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())
arr = list(map(int, input().split()))
stk = []
cnt = []
for i in range(n):
	if len(cnt) > 1 and cnt[-1] & 1 == 0:
		stk.pop()
		y = cnt.pop()
		cnt[-1] += y
	if len(stk) == 0:
		stk.append(arr[i])
		cnt.append(1)
	elif abs(stk[-1] - arr[i]) & 1 == 1:
		stk.append(arr[i])
		cnt.append(1)
	else:
		cnt[-1] += 1
for i in range(len(cnt) - 1):
	if cnt[i] % 2 == 1 and cnt[i + 1] % 2 == 1:
		print('No')
		exit()
print('Yes')


s = int(input())
arr = list(map(int, input().split()))
stack = []
for data in arr:
	if stack and stack[-1] == data % 2:
		stack.pop(-1)
	else:
		stack.append(data % 2)
if len(stack) <= 1:
	print('YES')
else:
	print('NO')


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