Alex, Bob and Carl will soon participate in a team chess tournament. Since they are all in the same team, they have decided to practise really hard before the tournament. But it's a bit difficult for them because chess is a game for two players, not three.

So they play with each other according to following rules:  Alex and Bob play the first game, and Carl is spectating;  When the game ends, the one who lost the game becomes the spectator in the next game, and the one who was spectating plays against the winner. 

Alex, Bob and Carl play in such a way that there are no draws.

Today they have played n games, and for each of these games they remember who was the winner. They decided to make up a log of games describing who won each game. But now they doubt if the information in the log is correct, and they want to know if the situation described in the log they made up was possible (that is, no game is won by someone who is spectating if Alex, Bob and Carl play according to the rules). Help them to check it!


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 100) — the number of games Alex, Bob and Carl played.

Then n lines follow, describing the game log. i-th line contains one integer a_{i} (1 ≤ a_{i} ≤ 3) which is equal to 1 if Alex won i-th game, to 2 if Bob won i-th game and 3 if Carl won i-th game.


-----Output-----

Print YES if the situation described in the log was possible. Otherwise print NO.


-----Examples-----
Input
3
1
1
2

Output
YES

Input
2
1
2

Output
NO



-----Note-----

In the first example the possible situation is:  Alex wins, Carl starts playing instead of Bob;  Alex wins, Bob replaces Carl;  Bob wins. 

The situation in the second example is impossible because Bob loses the first game, so he cannot win the second one.

Difficulty: interview

Starter code:

Solutions:
from collections import Counter, defaultdict
import itertools
import sys

def main():
    n = int(input())
    spec = 3
    poss = True
    for _ in range(n):
        winner = int(input())
        if winner != spec:
            spec = 6 - winner - spec
        else:
            poss = False
    print('YES' if poss else 'NO')



main()


import itertools
import re
import math
import getpass
import sys
import string

debug = getpass.getuser() == 'frohe'
files = True

if debug and files:
    sys.stdin = open('test.in')
else:
    pass
    # sys.stdin = open('schools.in')
    # sys.stdout = open('schools.out', 'w')


def ria():
    return [int(i) for i in input().split()]


n = ria()[0]
pl = [1, 2]
sp = 3
for i in range(n):
    wn = ria()[0]
    if wn not in pl:
        print('NO')
        return

    pl = [wn] + [sp]
    spn=[1,2,3]
    for j in pl:
        spn.remove(j)
    sp=spn[0]
print('YES')

n = int(input())
spec = 3
for i in range(n):
    k = int(input())
    if k == spec:
        print("NO")
        break
    spec = list(set([1, 2, 3]) - set([k, spec]))[0]
else:
    print("YES")


#map(int, input().split())
n = int(input())
a = [1, 2]
d = [1, 2, 3]
for i in range(n):
    aa = int(input())
    if aa in a:
        ii = (a.index(aa) + 1) % 2
        for j in range(3):
            if d[j] not in a:
                a[ii] = d[j]
                break
    else:
        print('NO')
        return
print('YES')


n = int(input())
p = 3
for i in range(n):
    x = 1 << (int(input()) - 1)
    if x & p:
        p ^= 7
        p |= x
    else:
        p = -1
        break
print('YES' if p!=-1 else 'NO')

x = int(input())
k = [1, 2]
w = 0
for i in range(x):
	n = int(input())
	if k.count(n) == 0:
		w = 1
		break
	k[1 - k.index(n)] = 6 - k[0] - k[1]
if w == 1:
	print('NO')
else:
	print('YES')


n=int(input())
a,b=1,2
c=3
m=[]
for i in range(n):
    m.append(int(input()))
for x in m:
    if x==a:
        b,c=c,b
    elif x==b:
        a,c=c,a
    else:
        print('NO')
        break
else:
    print('YES')


n = int(input())

correct = True

A = set([1, 2])
spect = 3

for _ in range(n):
    tmp = int(input())
    if tmp not in A:
        correct = False
        break
    A, spect = set([spect, tmp]), list(A.difference(set([tmp])))[0]


if correct:
    print("YES")
else:
    print("NO")


n = int(input())
players = [1, 2]
nub = 3
for i in range(n):
    a = int(input())
    if a in players:
        if players[0] == a:
            b = nub
            nub = players[1]
            players = [a, b]
        else:
            b = nub
            nub = players[0]
            players = [a, b]
    else:
        print('NO')
        break
else:
    print('YES')

n=int(input())
prev=0
play=[1,2]
for x in range(n):
    a=int(input())
    if a not in play:
        print('NO')
        break
    play=[x for x in range(1,4) if (x not in play) or (x in play and x==a)]
    #print(play)
else:
    print('YES')

n = int(input())
spectator = 3
for _ in range(n):
    cur = int(input())
    if cur == spectator:
        print('NO')
        break
    spectator = {1, 2, 3}.difference({spectator, cur}).pop()
else:
    print('YES')



def solve():
    on1 = 1
    on2 = 2
    off = 3
    for i in range(int(input())):
        win = int(input())
        if win == on1:
            on2, off = off, on2
        elif win == on2:
            on1, off = off, on1
        else:
            return 'NO'

    return 'YES'
print(solve())

q=int(input())
b=True
w=int(input())
if w==3:
    b=False
t=set([1,2,3])
g=set([w,3])
for i in range(1,q):
    w=int(input())
    if w not in g:
        b=False
    g={w}|(t-g)
print('YES' if b else 'NO')


l = [int(input()) for _ in range(int(input()))]
p = {1, 2}
for e in l:
	if e in p:
		p = {1, 2, 3} - p | {e}
	else:
		print("NO")
		return
print("YES")


# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

"""
created by shhuan at 2017/11/23 23:06

"""

N = int(input())


players = {1, 2}

for i in range(N):
    a = int(input())
    if a not in players:
        print("NO")
        return

    np = {1, 2, 3} - players

    players = np | {a}

print("YES")

n = int(input())
f = True
a = 1
b = 2
for i in range(n):
    k = int(input())
    if k != a and k != b:
        f = False
    l = [a, b]
    if 1 not in l:
        b = 1
    elif 2 not in l:
        b = 2
    else:
        b = 3
    a = k
    if k == b:
        f = False
if f:
    print("YES")
else:
    print("NO")

import sys
n = int(input())
for i in range(n):
    if i == 0:
        winner = 1
        looser = 2
        looker = 3
        a = int(input())
        if a == 3:
            print("NO")
            return
        if a == 1:
            looser, looker = looker, looser
        else:
            winner, looker = looker, winner
        continue
    a = int(input())
    if a == looker:
        print("NO")
        return
    if a == winner:
        looser, looker = looker, looser
    else:
        winner, looker = looker, winner
print("YES")

n = int(input())
c = 3
g = True
for i in range(n):
    t = int(input())
    if t == c:
        g = False
    else:
        c = list({1, 2, 3} ^ {t, c})[0]
if g:
    print("YES")
else:
    print("NO")



n = int(input())
a = [int(input()) for i in range(n)]

p1, p2, p3 = 1, 2, 3
for i in a:
    if p1 != i and p2 != i:
        print('NO')
        return
    elif p1 != i:
        p1, p3 = p3, p1
    else:
        p2, p3 = p3, p2

print('YES')




def R():
	return list(map(int,input().strip().split()))

n = int(input())
possible = [1,1,0]
pos = True
for i in range(n):
	a = int(input())
	if possible[a-1]!=1:
		pos = False
	for j in range(3):
		if possible[j]==1 and a!=j+1:
			possible[j] = 0
			continue
		if possible[j]==0:
			possible[j] = 1

if pos:
	print("YES")
else:
	print("NO")


n = int(input())

gamers = {1: True, 2: True, 3: False}

for i in range(n):
    a = int(input())

    if not gamers[a]:
        print('NO')
        return

    else:
        for j in list(gamers.keys()):
            if j != a:
                gamers[j] = not gamers[j]

print('YES')


def main():
    read = lambda: tuple(map(int, input().split()))
    n = read()[0]
    state = [1, 1, 0]
    def f(x, state):
        for i in range(3):
            if i != x:
                state[i] = 1 - state[i]
    #print(n, state)
    for i in range(n):
        c = read()[0] - 1
        if state[c] == 0:
            return "NO"
        f(c, state)
    return "YES"
print(main())


n = int(input())
ind1, ind2  = 1, 2
indicator = True
for i in range(n):
	a = int(input())
	if a != ind1 and a != ind2:
		indicator = False
		print("NO")
		break
	else:
		ind1, ind2 = a, 6 - (ind1 + ind2)
if indicator:
	print("YES")



k = int(input().strip().split()[0])
sp = 3
answer = "YES"
for _ in range(k):
    i = int(input().strip().split()[0])
    if i == sp:
        answer = "NO"
        break
    else:
        sp = 6 - i - sp
print(answer)

def solution(games):
    current_players = [True, True, False]

    for winner in games:
        if not current_players[winner - 1]:
            return False

        current_players = [
            True if winner - 1 == player else not current_players[player]
            for player in range(3)
        ]

    return True

n = int(input())
games = [int(input()) for i in range(n)]

print("YES" if solution(games) else "NO")