A camera you have accidentally left in a desert has taken an interesting photo. The photo has a resolution of n pixels width, and each column of this photo is all white or all black. Thus, we can represent the photo as a sequence of n zeros and ones, where 0 means that the corresponding column is all white, and 1 means that the corresponding column is black.

You think that this photo can contain a zebra. In this case the whole photo should consist of several (possibly, only one) alternating black and white stripes of equal width. For example, the photo [0, 0, 0, 1, 1, 1, 0, 0, 0] can be a photo of zebra, while the photo [0, 0, 0, 1, 1, 1, 1] can not, because the width of the black stripe is 3, while the width of the white stripe is 4. Can the given photo be a photo of zebra or not?


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 100 000) — the width of the photo.

The second line contains a sequence of integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 1) — the description of the photo. If a_{i} is zero, the i-th column is all black. If a_{i} is one, then the i-th column is all white.


-----Output-----

If the photo can be a photo of zebra, print "YES" (without quotes). Otherwise, print "NO".

You can print each letter in any case (upper or lower).


-----Examples-----
Input
9
0 0 0 1 1 1 0 0 0

Output
YES

Input
7
0 0 0 1 1 1 1

Output
NO

Input
5
1 1 1 1 1

Output
YES

Input
8
1 1 1 0 0 0 1 1

Output
NO

Input
9
1 1 0 1 1 0 1 1 0

Output
NO



-----Note-----

The first two examples are described in the statements.

In the third example all pixels are white, so the photo can be a photo of zebra.

In the fourth example the width of the first stripe is equal to three (white color), the width of the second stripe is equal to three (black), and the width of the third stripe is equal to two (white). Thus, not all stripes have equal length, so this photo is not a photo of zebra.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
x = list(map(int, input().split()))
d = None
s = 1
c = x[0]
for i in range(1, n):
    if x[i] == c:
        s += 1
    else:
        if d is None:
            d = s
        else:
            if (s != d):
                print("NO")
                break
        s = 1
        c = x[i]
else:
    if (d is None) or (s == d):
        print("YES")
    else:
        print("NO")


n = int(input())
l = list(map(int, input().split()))
s = ''
for i in range(n):
	s += str(l[i])
j = 0
while j != n and l[j] == l[0]:
	j += 1
ans = ''
blocks = n // j
curr = l[0]
for i in range(blocks):
	ans += j * str(curr)
	curr ^= 1
if ans == s:
	print("YES")
else:
	print("NO")

n = int(input())
stripes = [int(x) for x in input().split()] + [-1]
ln = 1
while ln < n and stripes[ln] == stripes[ln - 1]:
    ln += 1
cur = ln
flag = True
for i in range(ln, n + 1):
    if stripes[i] != stripes[i - 1]:
        if cur != ln:
            flag = False
            break
        cur = 0
    cur += 1
if flag:
    print('YES')
else:
    print('NO')

n = int(input())
line = list(map(int, input().split()))
ans = [1]
prev = line[0]
k = 1
for i in range(1, n):
    if line[i] == prev:
        ans[-1] += 1
    else:
        k += 1
        prev = line[i]
        ans.append(1)
if [ans[0]] * k != ans:
    print('NO')
else:
    print('YES')


input()

picture = input().split()

cur_col = picture[0]
cur_len = 0
last_len = -1


for i in picture:
	if i == cur_col:
		cur_len += 1
	else:
		if last_len != -1 and cur_len != last_len:
			print("NO")
			return
		else:
			last_len = cur_len
			cur_len = 1
			cur_col = i
			
if last_len != -1 and cur_len != last_len:
	print("NO")
	return

print("YES")


n = int(input())
arr = list(map(int, input().split()))
i = 0
last = 0
now = 0
ln = -1
flag = 0
for i in range(len(arr)):
    if arr[i] == arr[last]:
       now += 1
    else:
        if not (ln == -1 or ln == now):
            flag = 1
            break
        elif ln == -1:
            ln = now
            last = i
            now = 1
        else:
            last = i
            now = 1


if not flag and (ln == -1 or ln == now):
    print("YES")
else:
    print("NO")

n = int(input())
a = [int(i) for i in input().split()]
cnt = 0
curcnt = 0
cur = a[0]
for i in range(n):
	if a[i]==cur:
		curcnt+=1
	else:
		break

cnt = curcnt*1
if cnt==n: 
	print('YES')
else:

	curcnt = 0
	cur = a[i]
	br = 0
	for i in range(i, n):
		if a[i]==cur:
			curcnt+=1
			# print('+', end=' ')
		else:
			
			cur = a[i]
			if curcnt!=cnt:
				# print(cur, curcnt, cnt, '!')
				br = 1
				break
			curcnt = 1
	if curcnt!=cnt:
		br = 1


	if br:
		print('NO')
	else:
		print('YES')




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

len = -1
lastColor = -1
curLen = 0
a.append(-1)


for i in a:
    if i != lastColor:
        if len != -1:
            if curLen != len:
                print("NO")
                return
        else:
            if lastColor != -1:
                len = curLen
        lastColor = i
        curLen = 1
    else:
        curLen += 1

print("YES")


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

if a.count(0) == n or a.count(1) == n:
    print('YES')
    return

w = a.index(not a[0])

if n % w != 0:
    print('NO')
    return

for i in range(n // w):
    if a[w * i: w * (i + 1)] != [(i % 2 + a[0]) % 2 for _ in range(w)]:
        print('NO')
        return

print('YES')


len = int(input())
line = input().split(' ')

cnt = 1
i = 1

while i < len:
	if line[i] != line[i - 1]:
		cnt = cnt + 1
	i = i + 1

need_len = len // cnt

if need_len * cnt != len:
	print("NO")
else:
	i = 0
	while i < len:
		size = 0
		if int(line[i]) == 1:
			while i < len and int(line[i]) == 1:
				i = i + 1
				size = size + 1
		else:
			while i < len and int(line[i]) == 0:
				i = i + 1
				size = size + 1
		if size != need_len:
			print("NO")
			i = len + 100
	if i - 10 < len:
		print("YES")	


n = int(input())
a = input().split()
now = -1
white = 0
black = 0
for i in range(n):
    if(int(a[i]) == 0):
        if(white > 0):
            if(now == -1):
                now = white
            elif(now != white):
                print("NO")
                return
        
        white = 0
        black += 1
    else:
        if(black > 0):
            if(now == -1):
                now = black
            elif(now != black):
                print("NO")
                return
        black = 0
        white += 1

if(white > 0):
    if(now == -1):
        now = white
    elif(now != white):
        print("NO")
        return

if(black > 0):
    if(now == -1):
        now = black
    elif(now != black):
        print("NO")
        return
        
print("YES")

n = input()
line = [int(x) for x in input().split()]

current = line[0]
current_size = 1
line_size = -1

for i in line[1:]:
    if i == current:
        current_size = current_size + 1
        if current_size > line_size != -1:
            print("NO")
            return
    if i != current:
        if current_size !=  line_size and line_size!= -1:
            print("NO")
            return
        line_size = current_size
        current = i
        current_size = 1

if current_size != line_size and line_size!= -1:
    print("NO")
    return
print("YES")

q = int(input())
cnt1 = 0
cnt2 = 0
flag = 0
a = list(map(int, input().split()))
l = a[0]
for i in range(q):
    if (a[i] == 0):
        if ((l != a[i]) and (cnt1 != 0) and (cnt2 != 0)):
            if (cnt1 != cnt2):
                flag = 1
            cnt1 = 0
        cnt1 += 1
    else:
        if ((l != a[i]) and (cnt2 != 0) and (cnt1 != 0)):
            if (cnt1 != cnt2):
                flag = 1
            cnt2 = 0
        cnt2 += 1
    l = a[i]
if ((cnt1 != cnt2) and (cnt1 != 0) and (cnt2 != 0)):
    flag = 1
if (flag == 1):
    print("NO")
else:
    print("YES")

n = int(input())
ln = 0
start = 1
last = -1
check = 1
x = list(map(int, input().split()))
for i in range(n):
    num = x[i]
    if num != last:
        if ln == 0:
            ln = i + 1 - start
        else:
            if i + 1 - start != ln:
                check = 0
        start = i + 1
    last = num
if ln != 0 and n + 1 - start != ln:
    check = 0
if check == 0:
    print('NO')
else:
    print('YES')

n = int(input())
a = list(map(int, input().split()))
last = -1
cnt = 0
fx = -1
kek = 0
for i in range(0, n):
    cur = a[i]
    if last == -1:
        cnt = cnt + 1
    elif last == cur:
        cnt = cnt + 1
    else:
        if fx == -1:
            fx = cnt
        elif fx != cnt:
            kek = -1
        cnt = 1
    last = cur
if fx == -1:
    fx = cnt
elif fx != cnt:
    kek = -1
if kek == -1:
    print("NO")
else:
    print("YES")

n = int(input())
a = list(map(int, input().split()))
cnt = 0
cnt1 = 0
cnt2 = 0
p = -1
flag = True
for i in range(n):
    if a[i] == 1:
        if p != 1:
            if cnt != cnt1 and cnt != 0:
                flag = False
            cnt = cnt1
            p = 1
            cnt1 = 0
        cnt1 += 1
    if a[i] == 0:
        if p != 0:
            if cnt != cnt1 and cnt != 0:
                flag = False
            cnt = cnt1
            cnt1 = 0
            p = 0
        cnt1 += 1
if cnt != cnt1 and cnt != 0:
    flag = False
if flag:
    print('YES')
else:
    print('NO')

n = int(input());
s = map(int, input().split());
i = 0;
k = 0;
t = 0;
x = 0;
c = 0;
ans = 1;
for i in list(s):
    p = int(i);
    if (c == 0):
        if (k == 0):
            t = p;
        if (t == p):
            k += 1
        else:
            t = p;
            x = 0;
            c = 1;
    if (t == p):
        x += 1
    else:
        t = p;
        if (x != k):
            ans = 0;
        x = 1;
if (x != k):
    ans = 0;
if (ans == 1):
    print('YES')
else:
    print('NO')

# python3



n = input()
a = list(map(int, input().split()))
len=0

n=int(n)

len=0

for i in range (1,n):
    sc = a[i]-a[i-1]
    if(sc>0):
        len=i
        break
    if(sc<0):
        len=i
        break
fl=1;
if(len==0): 
    len=n
r=n%len
if(r==0):
    lol=1
else:
    print("NO")
    return
for i in range (1,n):
    sc = a[i]-a[i-1]
    if(sc>0):
        tmp = (i)%len
        if(tmp>0):
            fl=0
        if(tmp<0):
            fl=0
    if(sc<0):
        tmp = (i)%len
        if(tmp>0):
           fl=0
        if(tmp<0):
            fl=0
    if(sc==0):
        tmp = (i)%len
        if(tmp==0):
            fl=0
if(fl==0):
    print ("NO")
else:
    print("YES")

n = int(input())
a = list(map(int, input().split()))
v = list()
last, cnt = a[0], 0
for i in range(n):
	if a[i] == last:
		cnt += 1
	else:
		v.append(cnt)
		cnt = 1
		last = a[i]
v.append(cnt)

f = True
for e in v:
	if e != v[0]:
		f = False

if (f):
	print('YES')
else:
	print('NO')


def solve():
    n = int(input())
    p = [int(x) for x in (input().split())]
    c = dict()
    cnt = 0
    for i in range(n):
        if i == 0:
            cnt += 1
            continue
        if p[i] == p[i - 1]:
            cnt += 1
        if p[i] != p[i - 1]:
            c[cnt] = 1
            cnt = 1
        if i == n - 1:
            c[cnt] = 1
    if len(c) < 2:
        print('YES')
    else:
        print('NO')
 
solve()


n = int(input())
a = input().split()
for j in range(n):
  a[j] = int(a[j])
i = 1
last = a[0]
count = 1;
while (i < n and last == a[i]):
	i+=1
	count+=1
if (i < n):
	last = a[i]
	buf = 1
	i += 1
	flag = 1
	while (i < n):
		if (last == a[i]):
			buf += 1
		else:
			if (count != buf):
				flag = 0
				break
			else:
				last = a[i]
				buf = 1
		i += 1
	if ((count != buf) or (flag == 0)):
		print("NO")
	else:	
		print("YES")
else:
	print("YES")

n = int(input())
a = input().split()
s = ''.join(a)
w = set(s.split('0')) - {''}
b = set(s.split('1')) - {''}
if len(w) > 1 or len(b) > 1:
	print("NO")
elif len(w) == 0 or len(b) == 0:
	print("YES")
elif len(list(w)[0]) == len(list(b)[0]):
	print("YES")
else:
	print("NO")

def main():
    n = int(input())
    photo = [int(x) for x in (input().split())]
    color = dict()
    cnt = 0
    for i in range(n):
        if i == 0:
            cnt += 1
            continue
        if photo[i] == photo[i - 1]:
            cnt += 1
        if photo[i] != photo[i - 1]:
            color[cnt] = 1
            cnt = 1
        if i == n - 1:
            color[cnt] = 1
    if len(color) <= 1:
         print('YES')
    else:
        print('NO')

main()

N=int(input())
arr=list(map(int, input().split(' ')[:N]))
i = 0
comp = 0
while i < N and arr[i] == arr[0]:
    comp += 1
    i += 1
flag = True
while i < N:
    c2 = 0
    check = arr[i]
    while i < N and arr[i] == check:
        i += 1
        c2 += 1
    if comp != c2:
        flag = False
if flag == True:
    print('YES')
else:
    print('NO')