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

Starter code:

Solutions:
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]
    else :
        if 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()))
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")
else:
    if b==0 or b==1:
        print("YES")
    else:
        print("NO")

#!/usr/bin/env python
# coding: utf-8

# In[4]:


import math
n=int(input())
columns=list(map(int, input().rstrip().split()))


# In[5]:


modcolumns=[i%2 for i in columns]


# In[6]:


test=0


# In[7]:


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


# In[ ]:




n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
    a[i] %= 2
    if len(b) != 0:
        if b[-1] == a[i]:
            b.pop()
        else:
            b.append(a[i])
    else:
        b.append(a[i])
if len(b) > 1:
    print("NO")
else:
    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")


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




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

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


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

# cook your dish here
n = int(input())

arr = list(map(int, input().split()))
arr = list([x%2 for x in 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()))
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())
l=[]
for i in input().split():
    tmp=1&int(i)
    if l==[] or l[-1]!=tmp: l.append(tmp)
    else: l.pop()

print("YES" if len(l)<2 else "NO")

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


#try from left
#try from right
if n == 1:
    print("YES")
else:
    # update all to parity
    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")
        
    # fix differences in parity
    else:
        if 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")

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 # if sum_l = 0 return YES else return NO
        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
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")
    return

if n==2:
    if A2[0]!=A2[1]:
        print("NO")
        return
    else:
        print("YES")
        return

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


#!/usr/bin/env python3                            
import sys                                        
                                                  
def rint():                                       
    return map(int, sys.stdin.readline().split()) 
#lines = stdin.readlines()                        
# ae : [h, l], height, length                     
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                               
    else:                                         
        if 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])                    
        else:                                     
            if e[h] == stack[-1]:                 
                stack.pop()                       
            else:                                 
                stack.append(e[h])                
if len(stack) > 1:                                
    print("NO")                                   
else:                                             
    print("YES")                                  

n=int(input())
a=list(map(int,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");return
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")
    

             
             
             


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


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')
else:
    if removed >= len(S)-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)

n = len(l_binary)
if n <= 1:
    print("YES")
else:
    print("NO")