For a [permutation] P of the integers 1 to N, we define a new array A_{P} of length N-2 as follows:

For 1 ≤ i ≤ N-2, (A_{P})_i denotes the number of [inversions] in the subarray P[i : i+2], i.e, the number of inversions in the array [P_{i}, P_{i+1}, P_{i+2}].

You are given an array A of length N, all of whose elements lie between 0 and 3. Does there exist a permutation P of length N+2 such that A_{P} = A?

------ Input Format ------ 

- The first line of input will contain one integer T, the number of test cases. The description of T test cases follows.
- Each test case consists of two lines of input.
- The first line of each test case contains a single integer N, the size of A.
- The second line of each test case contains N space-separated integers — the values of A_{1}, A_{2}, \ldots, A_{N}.

------ Output Format ------ 

For each test case, output in a single line the answer — \texttt{YES} if a permutation that satisfies the given conditions exists, and \texttt{NO} otherwise.

The output is not case sensitive, so for example the strings \texttt{YES, Yes, yES}, etc. will all be treated as correct. 

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 3$
- The sum of $N$ over all test cases doesn't exceed $10^{5}$

----- Sample Input 1 ------ 
4
4
0 1 3 2
4
0 1 2 3
4
0 0 0 0
5
0 1 2 1 0
----- Sample Output 1 ------ 
YES
NO
YES
NO
----- explanation 1 ------ 
Test case $1$: Consider $P = [1, 2, 6, 5, 3, 4]$. It can be verified that $A_{P} = [0, 1, 3, 2]$. There are other permutations which give the same array — for example $[2, 3, 6, 5, 1, 4]$ and $[3, 4, 6, 5, 1, 2]$.

Test case $2$: It can be verified that no permutation $P$ of length $6$ has $A_{P} = [0, 1, 2, 3]$.

Test case $3$: The only permutation that satisfies the condition is $P = [1, 2, 3, 4, 5, 6]$.

Test case $4$: It can be verified that no permutation $P$ of length $7$ has $A_{P} = [0, 1, 2, 1, 0]$

Difficulty: HARD
Tags: Number theory

Combinatorics

Starter code:

Solutions:
def loop(n, p, flag, a):
	for i in range(n):
		count = 0
		if p[-1] < p[-2]:
			count += 1
		count1 = count2 = count3 = count
		count2 += 2
		count3 += 1
		if count1 == a[i]:
			p.append(max(p[-1], p[-2]) + 1)
		elif count2 == a[i]:
			p.append(min(p[-1], p[-2]) - 1)
		elif count3 == a[i]:
			p.append((p[-1] + p[-2]) / 2)
		else:
			flag[0] = 0
			break
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p = [1, 2]
	flag = [1]
	loop(n, p, flag, a)
	if flag[0] == 1:
		print('YES')
	else:
		flag[0] = 1
		p = [2, 1]
		loop(n, p, flag, a)
		if flag[0] == 1:
			print('YES')
		else:
			print('NO')


def loop(n, p, flag, a):
	for i in range(n):
		t1 = p[-1]
		t2 = p[-2]
		nxt = max(t1, t2) + 1
		count1 = 0
		if t1 < t2:
			count1 += 1
		if nxt < t1:
			count1 += 1
		if nxt < t2:
			count1 += 1
		if count1 == a[i]:
			p.append(nxt)
		nxt = min(t1, t2) - 1
		count2 = 0
		if t1 < t2:
			count2 += 1
		if nxt < t1:
			count2 += 1
		if nxt < t2:
			count2 += 1
		if count2 == a[i]:
			p.append(nxt)
		nxt = (t1 + t2) / 2
		count3 = 0
		if t1 < t2:
			count3 += 1
		if nxt < t1:
			count3 += 1
		if nxt < t2:
			count3 += 1
		if count3 == a[i]:
			p.append(nxt)
		if count1 != a[i] and count2 != a[i] and (count3 != a[i]):
			flag[0] = 0
			break
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p = [1, 2]
	flag = [1]
	loop(n, p, flag, a)
	if flag[0] == 1:
		print('YES')
	else:
		flag[0] = 1
		p = [2, 1]
		loop(n, p, flag, a)
		if flag[0] == 1:
			print('YES')
		else:
			print('NO')


lookup = {}
lookup[0] = ['UU']
lookup[1] = ['UD', 'DU']
lookup[2] = ['DU', 'UD']
lookup[3] = ['DD']
comb = {}
for i in range(4):
	for j in range(4):
		key = (i, j)
		comb[key] = []
		for num1 in lookup[i]:
			for num2 in lookup[j]:
				if num1[1] == num2[0]:
					comb[key].append(num2)
for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	if n == 1:
		print('YES')
		continue
	ini = (arr[0], arr[1])
	if not comb[ini]:
		print('NO')
	else:
		if n == 2:
			print('YES')
			continue
		ans = 'NO'
		for pos in comb[ini]:
			pref = True
			curr = pos[1]
			for i in range(2, n):
				found = False
				local_key = (arr[i - 1], arr[i])
				for num in comb[local_key]:
					if num[0] == curr:
						curr = num[1]
						found = True
						break
				if not found:
					pref = False
					break
			if pref:
				ans = 'YES'
				break
		print(ans)


def mgc(arr):
	if arr[0] == 0:
		temp1 = [1, 2, 3]
		temp2 = None
	elif arr[0] == 1:
		temp1 = [1, 3, 2]
		temp2 = [2, 1, 3]
	elif arr[0] == 2:
		temp1 = [3, 1, 2]
		temp2 = [2, 3, 1]
	else:
		temp1 = [3, 2, 1]
		temp2 = None
	for i in arr[1:]:
		if i == 0:
			if temp2:
				temp2 = None
			elif temp1[1] > temp1[2]:
				return False
			temp1 = [1, 2, 3]
		elif i == 1:
			if temp2:
				temp1 = [1, 3, 2]
				temp2 = [2, 1, 3]
			elif temp1[1] > temp1[2]:
				temp1 = [2, 1, 3]
			else:
				temp1 = [1, 3, 2]
		elif i == 2:
			if temp2:
				temp1 = [3, 1, 2]
				temp2 = [2, 3, 1]
			elif temp1[1] > temp1[2]:
				temp1 = [3, 1, 2]
			else:
				temp1 = [2, 3, 1]
		else:
			if temp2:
				temp2 = None
			elif temp1[1] < temp1[2]:
				return False
			temp1 = [3, 2, 1]
	return True
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = mgc(arr)
	if ans:
		print('YES')
	else:
		print('NO')


def answer():
	(what, prev) = (-1, -1)
	for i in range(n):
		if a[i] == 0 or a[i] == 3:
			if what == a[i]:
				if i - prev & 1 == 0:
					return 'NO'
			elif what != -1:
				if i - prev & 1:
					return 'NO'
			(what, prev) = (a[i], i)
	return 'YES'
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(answer())


def solve(ar, n):
	l = []
	for i in range(n):
		if ar[i] == 0 or ar[i] == 3:
			l.append([ar[i], i])
			if len(l) == 1:
				continue
			if l[0][0] == l[1][0]:
				if (l[1][1] - l[0][1]) % 2 == 0:
					return False
			elif (l[1][1] - l[0][1]) % 2 == 1:
				return False
			l.pop(0)
	return True
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if solve(l, n):
		print('YES')
	else:
		print('NO')


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	res = 'YES'
	f = 0
	if a[0] == 0:
		f = 1
	if a[0] == 3:
		f = 2
	for i in range(1, n):
		if a[i] == 0:
			if f == 2:
				res = 'NO'
				break
			else:
				f = 1
		elif a[i] == 3:
			if f == 1:
				res = 'NO'
				break
			else:
				f = 2
		elif a[i] == 1:
			if f == 1:
				f = 2
			elif f == 2:
				f = 1
		elif f == 1:
			f = 2
		elif f == 2:
			f = 1
	print(res)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = []
	for i in range(N):
		if A[i] == 0 or A[i] == 3:
			B.append((A[i], i))
	stat = 1
	for i in range(len(B) - 1):
		steps = B[i + 1][1] - B[i][1]
		if B[i + 1][0] != B[i][0]:
			if steps % 2 != 0:
				stat = 0
				break
		elif steps % 2 == 0:
			stat = 0
			break
	if stat:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	arr = []
	for i in range(len(nums)):
		if nums[i] == 0 or nums[i] == 3:
			arr.append((nums[i], i))
	flag = 0
	for i in range(len(arr) - 1):
		steps = arr[i + 1][1] - arr[i][1]
		if arr[i][0] == arr[i + 1][0]:
			if steps % 2 == 0:
				flag = 1
				break
		elif steps % 2 != 0:
			flag = 1
			break
	if flag == 0:
		print('YES')
	else:
		print('NO')


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

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

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

def inpu():
	return int(inp())

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 fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(1, how_much_noob_I_am + 1):
		n = inpu()
		arr = lis()
		ans = []
		for i in range(n):
			if arr[i] in [0, 3]:
				ans.append([arr[i], i])
		ok = True
		for i in range(len(ans) - 1):
			if ans[i + 1][0] - ans[i][0] == 0:
				if (ans[i + 1][1] - ans[i][1]) % 2 != 0:
					ok &= True
				else:
					ok &= False
			elif (ans[i + 1][1] - ans[i][1]) % 2 == 0:
				ok &= True
			else:
				ok &= False
		if ok:
			print('YES')
		else:
			print('NO')
main()


for _ in range(int(input())):
	n = int(input())
	a = input().split()
	k = 0
	for i in a:
		if i == '3':
			if k == 2:
				print('NO')
				break
			k = 1
		elif i == '0':
			if k == 1:
				print('NO')
				break
			k = 2
		elif k == 2:
			k = 1
		elif k == 1:
			k = 2
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = True
	i = 0
	while i < n:
		if arr[i] != 1 or arr[i] == 2:
			break
		i += 1
	while i < n:
		c = 0
		j = i + 1
		while j < n:
			if arr[j] == 1 or arr[j] == 2:
				c += 1
				j += 1
			else:
				break
		if j == n:
			break
		if c % 2 == 0:
			if arr[i] == 0:
				if arr[j] == 3:
					ans = False
					break
			if arr[i] == 3 and arr[j] == 0:
				ans = False
				break
		else:
			if arr[i] == 0:
				if arr[j] == 0:
					ans = False
					break
			if arr[i] == 3 and arr[j] == 3:
				ans = False
				break
		i = j
	if ans:
		print('YES')
	else:
		print('NO')


addy = int(input())
for t in range(addy):
	n = int(input())
	l = list(map(int, input().split()))
	temp = 0
	f = 1
	for i in range(n):
		if i == 0:
			if l[i] == 0:
				temp = 0
			elif l[i] == 1 or l[i] == 2:
				temp = 0
			else:
				temp = 1
		elif temp:
			if l[i] == 0:
				f = 0
				break
			elif l[i] == 1 or l[i] == 2:
				temp = 0
			else:
				temp = 1
		elif l[i] == 0:
			temp = 0
		elif l[i] == 1 or l[i] == 2:
			temp = 1
		else:
			f = 0
			break
	g = 1
	for i in range(n):
		if i == 0:
			if l[i] == 0:
				temp = 0
			elif l[i] == 1 or l[i] == 2:
				temp = 1
			else:
				temp = 1
		elif temp:
			if l[i] == 0:
				g = 0
				break
			elif l[i] == 1 or l[i] == 2:
				temp = 0
			else:
				temp = 1
		elif l[i] == 0:
			temp = 0
		elif l[i] == 1 or l[i] == 2:
			temp = 1
		else:
			g = 0
			break
	if f | g:
		print('YES')
	else:
		print('NO')


import sys
sys.setrecursionlimit(10 ** 5)
maxN = 10 ** 5 + 5
A = [None] * 4
B = [None] * 4
A[0] = [[1, 1], [2, 0], [0, 0]]
A[1] = [[0, 0], [2, 0], [1, 1]]
B[1] = [[2, 1], [3, 0], [1, 0]]
A[2] = [[1, 0], [3, 0], [2, 1]]
B[2] = [[0, 0], [1, 1], [2, 0]]
A[3] = [[1, 0], [2, 1], [3, 0]]

def solve(data, pos, idx, n, accum):
	poss = True
	for i in range(n - 1):
		if pos[1] == 0:
			num = data[i + 1]
			p = None
			found = False
			for j in A[pos[0]]:
				if j[0] == num:
					p = j
					found = True
					break
			if found:
				pos = p
			else:
				poss = False
				break
		elif pos[1] == 1:
			num = data[i + 1]
			p = None
			found = False
			for j in B[pos[0]]:
				if j[0] == num:
					p = j
					found = True
					break
			if found:
				pos = p
			else:
				poss = False
				break
	accum[0] = poss

def main():
	t = int(input())
	while t > 0:
		t -= 1
		n = int(input())
		data = list(map(int, input().split()))
		if data[0] == 0 or data[0] == 3:
			accum = [True]
			solve(data, [data[0], 0], 0, n, accum)
			b = accum[0]
			if b:
				print('YES')
			else:
				print('NO')
		else:
			accum = [True]
			solve(data, [data[0], 0], 0, n, accum)
			b = accum[0]
			solve(data, [data[0], 1], 0, n, accum)
			b = b or accum[0]
			if b:
				print('YES')
			else:
				print('NO')
main()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(z, fail, c) = (0, False, 0)
	for i in range(len(arr)):
		item = arr[i]
		if item in [0, 3]:
			z = i
			break
	for i in arr[z + 1:]:
		if i == 0:
			if item == 3 and c % 2 == 0 or (item == 0 and c % 2 == 1):
				fail = True
				break
			(item, c) = (0, 0)
		elif i == 3:
			if item == 0 and c % 2 == 0 or (item == 3 and c % 2 == 1):
				fail = True
				break
			(item, c) = (3, 0)
		else:
			c += 1
	if fail:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	mp = [[] for _ in range(4)]
	mp[0].append('gg')
	mp[1].append('gl')
	mp[1].append('lg')
	mp[2].append('gl')
	mp[2].append('lg')
	mp[3].append('ll')
	q = []
	for i in range(len(mp[arr[0]])):
		q.append(mp[arr[0]][i])
	j = 1
	flagg = False
	while len(q):
		nn = len(q)
		if n == j:
			flagg = True
			print('YES')
			break
		z = arr[j]
		j += 1
		for i in range(nn):
			s = q[0]
			q = q[1:]
			for k in range(len(mp[z])):
				st = mp[z][k]
				if s[1] == st[0]:
					q.append(st)
	if flagg:
		continue
	print('NO')


def solve():
	n = int(input())
	l = list(map(int, input().split()))
	if l[False] == True or l[False] == 2:
		a = [False, True]
	elif l[False] == 3:
		a = [True]
	else:
		a = [False]
	for i in a:
		for j in range(n):
			if l[j] == 1 or l[j] == 2:
				i = not i
			elif l[j] == 3:
				if i == False:
					break
			elif i == True:
				break
		else:
			print('YES')
			break
	else:
		print('NO')
test_case = int(input())
while test_case > 0:
	solve()
	test_case -= 1


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(z, mode) = (0, -1)
	for t in range(len(arr)):
		i = arr[t]
		if i == 0 or i == 3:
			z = t
			if i == 0:
				mode = 1
			else:
				mode = 0
			break
	(wrong, count) = (False, 0)
	for i in arr[z + 1:]:
		if i == 0:
			if mode == 0 and count % 2 == 0 or (mode == 1 and count % 2 == 1):
				wrong = True
				break
			mode = 1
			count = 0
		elif i == 3:
			if mode == 1 and count % 2 == 0 or (mode == 0 and count % 2 == 1):
				wrong = True
				break
			mode = 0
			count = 0
		else:
			count += 1
	if wrong:
		print('NO')
	else:
		print('YES')


def process(curr, l):
	for k in range(1, len(l)):
		if l[k] == 0:
			if curr == 'u':
				return 'NO'
			else:
				curr = 's'
		if l[k] == 1:
			if curr == 'u':
				curr = 's'
			else:
				curr = 'u'
		if l[k] == 2:
			if curr == 'u':
				curr = 's'
			else:
				curr = 'u'
		if l[k] == 3:
			if curr == 's':
				return 'NO'
			else:
				curr = 'u'
	return 'YES'
t = int(input())
for i in range(t):
	n = int(input())
	j = 0
	l = list(map(int, input().split(' ')))
	curr = True
	if l[0] == 0:
		curr = 's'
		print(process(curr, l))
	elif l[0] == 3:
		curr = 'u'
		print(process(curr, l))
	elif process('s', l) == 'NO' and process('u', l) == 'NO':
		print('NO')
	else:
		print('YES')


tc = int(input())
for case in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	if a[0] == 1 or a[0] == 2:
		prev = [0, 1]
	elif a[0] == 3:
		prev = [1]
	else:
		prev = [0]
	for pr in prev:
		for i in range(n):
			if a[i] == 1 or a[i] == 2:
				if pr == 0:
					pr = 1
				else:
					pr = 0
			elif a[i] == 3:
				if pr == 1:
					pr = 1
				else:
					break
			elif pr == 0:
				pr = 0
			else:
				break
		else:
			print('YES')
			break
	else:
		print('NO')


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	flag = 0
	order = [[-1] * 4 for x in range(n + 2)]
	if a[0] == 0:
		order[1][2] = order[2][1] = 0
	if a[0] == 1 or a[0] == 2:
		order[1][2] = order[2][1] = 11
	if a[0] == 3:
		order[1][2] = order[2][1] = 3
	for x in range(1, n):
		b = order[x][2]
		if b == 0 and a[x] == 3:
			flag = 1
			break
		if b == 3 and a[x] == 0:
			flag = 1
			break
		if a[x] == 1 and b == 0:
			order[x + 1][2] = 3
		elif a[x] == 1 and b == 3:
			order[x + 1][2] = 0
		elif a[x] == 1:
			order[x + 1][2] = 11
		if a[x] == 2 and b == 0:
			order[x + 1][2] = 3
		elif a[x] == 2 and b == 3:
			order[x + 1][2] = 0
		elif a[x] == 2:
			order[x + 1][2] = 11
		if a[x] == 3:
			order[x + 1][2] = 3
		if a[x] == 0:
			order[x + 1][2] = 0
	if flag == 1:
		print('NO')
	else:
		print('YES')
	t -= 1


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	yesval = 'YES'
	lp = 0
	while lp < N and A[lp] != 0 and (A[lp] != 3):
		lp += 1
	rp = N - 1
	while rp > -1 and A[rp] != 0 and (A[rp] != 3):
		rp -= 1
	if rp >= lp and N != 1:
		cur = str(A[lp])
		for theta in range(lp + 1, rp + 1):
			arr_val = A[theta]
			if cur == '0' or cur == '1b' or cur == '2b':
				if arr_val == 0:
					cur = '0'
				elif arr_val == 1:
					cur = '1a'
				elif arr_val == 2:
					cur = '2a'
				elif arr_val == 3:
					yesval = 'NO'
					break
			elif cur == '3' or cur == '1a' or cur == '2a':
				if arr_val == 3:
					cur = '3'
				if arr_val == 1:
					cur = '1b'
				elif arr_val == 2:
					cur = '2b'
				elif arr_val == 0:
					yesval = 'NO'
					break
		print(yesval)
	else:
		print('YES')


tc = int(input())
for _ in range(tc):
	n = int(input())
	l = list(map(int, input().split()))
	d = {'00': ['00', '10', '21', '-1'], '11': ['00', '10', '21', '-1'], '20': ['00', '10', '21', '-1'], '10': ['-1', '11', '20', '30'], '21': ['-1', '11', '20', '30'], '30': ['-1', '11', '20', '30'], '01': ['-1', '-1', '-1', '-1'], '31': ['-1', '-1', '-1', '-1']}
	o = 0
	for c in '01':
		ok = True
		curr = str(l[0]) + c
		for i in range(n - 1):
			curr = d[curr][l[i + 1]]
			if curr == '-1':
				ok = False
				break
		if ok:
			print('YES')
			o = 1
			break
	if o == 0:
		print('NO')


adj_list = [[0, 1, 3], [2, 4, 5], [0, 1, 3], [2, 4, 5], [0, 1, 3], [2, 4, 5]]

def check_possible(arr, adj, start):
	for i in range(1, len(arr)):
		if arr[i] == 0:
			next1 = {0}
		elif arr[i] == 3:
			next1 = {5}
		elif arr[i] == 1:
			next1 = {1, 2}
		else:
			next1 = {3, 4}
		for ele in next1:
			if ele in adj_list[start]:
				start = ele
				break
		else:
			return False
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if a[0] == 1:
		check1 = check_possible(a, adj_list, 1)
		check2 = check_possible(a, adj_list, 2)
		if check1 == True or check2 == True:
			print('YES')
		else:
			print('NO')
	elif a[0] == 2:
		check1 = check_possible(a, adj_list, 3)
		check2 = check_possible(a, adj_list, 4)
		if check1 == True or check2 == True:
			print('YES')
		else:
			print('NO')
	elif a[0] == 0:
		check1 = check_possible(a, adj_list, 0)
		if check1 == True:
			print('YES')
		else:
			print('NO')
	else:
		check1 = check_possible(a, adj_list, 5)
		if check1 == True:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	f = True
	stack = []
	if arr[0] == 0:
		stack.append(1)
	elif arr[0] == 1:
		pass
	elif arr[0] == 2:
		pass
	else:
		stack.append(-1)
	for el in arr[1:]:
		if el == 0:
			if not stack or stack[-1] == 1:
				stack.append(1)
			else:
				f = False
				break
		elif el == 3:
			if not stack or stack[-1] == -1:
				stack.append(-1)
			else:
				f = False
				break
		elif el == 2:
			if not stack:
				pass
			elif stack[-1] == 1:
				stack.append(-1)
			elif stack[-1] == -1:
				stack.append(1)
		elif el == 1:
			if not stack:
				pass
			elif stack[-1] == 1:
				stack.append(-1)
			elif stack[-1] == -1:
				stack.append(1)
	if f:
		print('YES')
	else:
		print('NO')


import sys
from math import sqrt, gcd, factorial, ceil, floor
from collections import deque, Counter, OrderedDict
from heapq import heapify, heappush, heappop
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	n = I()
	a = L()
	ans = 'YES'
	if a[0] == 0:
		v = 1
	elif a[0] == 3:
		v = -1
	else:
		v = 0
	for i in range(1, n):
		if a[i] == 0:
			if v == -1:
				ans = 'NO'
				break
			else:
				v = 1
		elif a[i] == 3:
			if v == 1:
				ans = 'NO'
				break
			else:
				v = -1
		elif a[i] == 1:
			if v == 1:
				v = -1
			elif v == -1:
				v = 1
		elif v == 1:
			v = -1
		elif v == -1:
			v = 1
	print(ans)