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: introductory

Starter code:

Solutions:
#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        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())     #idle 中不会执行 atexit
    
N, = getIntList()
#print(N)
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))
    #dprint(duo)
print('YES')
            
    
    
    








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


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

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

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

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

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

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

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

if (len(l) ==1 and l[0] >= m) or len(l) == 0 :
    print('YES')
else:
    print('NO')




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

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

if (len(l) ==1 and l[0] >= m) or len(l) == 0 :
    print('YES')
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')

    else:
        if 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()

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










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]
	# print(a, currenth)
	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: # a[i + 1] < currenth
			stack.append((target, currenth, begin))
			# print(stack, i)
			i += 1
			target = currenth
			currenth = a[i]
			begin = i

res = build(0, M)
# print(res)
while res != -1 and res < n - 1:
	res = build(res + 1, M)
	print(res)
if res == n - 1:
	print('YES')
else:
	# print(build(0, M))
	print('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]
	# print(a, currenth)
	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: # a[i + 1] < currenth
			stack.append((target, currenth, begin))
			# print(stack, i)
			i += 1
			target = currenth
			currenth = a[i]
			begin = i

res = build(0, M)
# print(res)
while res != -1 and res < n - 1:
	res = build(res + 1, M)
	# print(res)
if res == n - 1:
	print('YES')
else:
	# print(build(0, M))
	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")

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
    else :
        if 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()))
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())
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())
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())
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()))
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")