Andrewid the Android is a galaxy-famous detective. He is now investigating a case of frauds who make fake copies of the famous Stolp's gears, puzzles that are as famous as the Rubik's cube once was.

Its most important components are a button and a line of n similar gears. Each gear has n teeth containing all numbers from 0 to n - 1 in the counter-clockwise order. When you push a button, the first gear rotates clockwise, then the second gear rotates counter-clockwise, the the third gear rotates clockwise an so on.

Besides, each gear has exactly one active tooth. When a gear turns, a new active tooth is the one following after the current active tooth according to the direction of the rotation. For example, if n = 5, and the active tooth is the one containing number 0, then clockwise rotation makes the tooth with number 1 active, or the counter-clockwise rotating makes the tooth number 4 active.

Andrewid remembers that the real puzzle has the following property: you can push the button multiple times in such a way that in the end the numbers on the active teeth of the gears from first to last form sequence 0, 1, 2, ..., n - 1. Write a program that determines whether the given puzzle is real or fake.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 1000) — the number of gears.

The second line contains n digits a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ n - 1) — the sequence of active teeth: the active tooth of the i-th gear contains number a_{i}.


-----Output-----

In a single line print "Yes" (without the quotes), if the given Stolp's gears puzzle is real, and "No" (without the quotes) otherwise.


-----Examples-----
Input
3
1 0 0

Output
Yes

Input
5
4 2 1 4 3

Output
Yes

Input
4
0 2 3 1

Output
No



-----Note-----

In the first sample test when you push the button for the first time, the sequence of active teeth will be 2 2 1, when you push it for the second time, you get 0 1 2.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
for i in range(n + 1):
    for j in range(n):
        if j % 2 == 0:
            a[j] = (a[j] + 1) % n
        else:
            a[j] = (a[j] - 1) % n
    for j in range(n):
        if a[j] != j:
            break
    else:
        print("Yes")
        return
print("No")


import sys

n = int(input())
a = list(map(int,input().split()))
for i in range(n+1) :
          for j in range(n) :
                    if j%2 : a[j]-=1
                    else : a[j]+=1
                    a[j]%=n
          if a==list(range(n)) :
                    print('Yes')
                    return
print('No')


n = int(input())
a = list(map(int, input().split()))
if a[0] == 0:
   r = 0
else:
   r = n - a[0]
f = True
for i in range(n):
   if i % 2 == 0:
      a[i] += r
   else:
      a[i] -= r
   a[i] = a[i] % n
   if i > 0 and  a[i] != a[i - 1] + 1:
       f = False
       print('No')
       break
if f:
  print('Yes')
   



def check(gears):
    for i in range(0, len(gears)):
        if gears[i]!=i:
            return False
    return True    

#print((0-1)%3)
n = int(input())
gears = [int(i) for i in input().split()]
saved = set()
while True:
    current = str(gears)
    if current in saved:
        break
    saved.add(current)
    for i in range(0, n):
        if i%2 == 0:
            gears[i] = (gears[i]+1)%n
        else:
            gears[i] = (gears[i]-1)%n
    if check(gears):
        break
    #print("HI")
if check(gears):
    print("Yes")
else:
    print("No")

import math,string,itertools,fractions,heapq,collections,re,array,bisect,copy
from itertools import chain, dropwhile, permutations, combinations
from collections import defaultdict, deque

# Guide:
#   1. construct complex data types while reading (e.g. graph adj list)
#   2. avoid any non-necessary time/memory usage
#   3. avoid templates and write more from scratch
#   4. switch to "flat" implementations

def VI(): return list(map(int,input().split()))
def I(): return int(input())
def LIST(n,m=None): return [0]*n if m is None else [[0]*m for i in range(n)]
def ELIST(n): return [[] for i in range(n)]
def MI(n=None,m=None): # input matrix of integers
    if n is None: n,m = VI()
    arr = LIST(n)
    for i in range(n): arr[i] = VI()
    return arr
def MS(n=None,m=None): # input matrix of strings
    if n is None: n,m = VI()
    arr = LIST(n)
    for i in range(n): arr[i] = input()
    return arr
def MIT(n=None,m=None): # input transposed matrix/array of integers
    if n is None: n,m = VI()
    a = MI(n,m)
    arr = LIST(m,n)
    for i,l in enumerate(a):
        for j,x in enumerate(l):
            arr[j][i] = x
    return arr


def run(n,a):
    for i in range(n+1):
        if a[0]==0:
            if sum([i==a[i] for i in range(n)])==n:
                print("Yes")
            else:
                print("No")
            return
        for j in range(n):
            if j%2==0:
                a[j] = (a[j]+1)%n
            else:
                a[j] = (a[j]-1)%n


def main(info=0):
    n = I()
    a = VI()

    run(n,a)



def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(1000000000)

n=int(input())
s=input().split()
t=[]
for i in range(n):
	t+=[int(s[i])]
x=0
if t[0]!=0:
	x=n-t[0]
bb=True
for i in range(n):
	if i%2==0 and (t[i]+x)%n!=i:bb=False
	if i%2==1 and (t[i]-x)%n!=i:bb=False
if bb:print("Yes")
else:print("No")


#!/usr/bin/env python3

N = int(input())
A = list(map(int, input().split(' ')))

def rotate(A):
	return [(a + (-1)**i) % N for i, a in enumerate(A)]

def ok(A):
	while True:
		A = rotate(A)
		if A[0] == 0:
			return A == list(range(N))

if ok(A):
	print('Yes')
else:
	print('No')

N = int(input())
G = [int(x) for x in input().split()]
trueG = list(range(N))
for i in range(N):
    for j in range(N):
        G[j] = (G[j] + (-1 if j % 2 else 1)) % N
    if G == trueG:
        print('Yes')
        break
else:
    print('No')
        
        


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

for _ in range(n+7):

	for i in range(n):
		if i%2 == 0:
			arr[i] += 1
			arr[i] %= n
		else:
			arr[i] -= 1
			if arr[i] == -1:
				arr[i] = n-1

	#print(arr)

	okay = True
	for i in range(n):
		if i != arr[i]:
			okay = False
			break

	if okay:
		print('Yes')
		return

print('No')

n = int(input())
gears = list(map(int, input().split()))
blah = sorted([i for i in range(n)])
good = False
for push in range(n):
    for i in range(len(gears)):
        if i % 2 == 0:
            gears[i] += 1
            if gears[i] == n:
                gears[i] = 0
        else:
            gears[i] -= 1
            if gears[i] == -1:
                gears[i] = n-1
    if gears == blah:
        print("Yes")
        good = True
        break
if not good:
    print("No")


from itertools import cycle
n = int(input())
l = list(map(int, input().split(' ')))

times_to_rotate = n - l[0]

for count, (i, mul) in enumerate(zip(l, cycle([1, -1]))):
    j = (i + times_to_rotate*mul) % n
    if j != count:
        print('No')
        break
else:
    print('Yes')



n = int(input())
a = [int(x) for x in input().split()]
diff = (n - a[0]) % n
for i in range(1, n):
    if i % 2 == 0:
        if (a[i] + diff) % n != i:
            #print((a[i] - diff) % n, i)
            print("No")
            return
    else:
        if (a[i] - diff) % n != i:
            #print((a[i] - diff) % n, i)
            print("No")
            return
print("Yes")


n = int(input())
#x, y = map(int, input().split(" "))
arr = input().split(" ")
for i in range(n):
    arr[i] = int(arr[i])

rotate = ( n - arr[0] ) % n
for i in range(1, n):
    if i%2 == 0:
        if (arr[i]+rotate) % n != i:
            print("No")
            quit()
    else: 
        if (arr[i]-rotate) % n != i:
            print("No")
            quit()

print("Yes")

def main():
    n = int(input())
    a = [int(t) for t in input().split()]
    shift = n - a[0]

    turn = 1
    out = 'Yes'
    for i in range(len(a)):
        a[i] = (a[i] + turn * shift) % n
        turn *= -1
        if a[i] != i:
            out = 'No'
            break

    print(out)

def __starting_point():
    main()
__starting_point()

n = int(input())
arr = list(map(int, input().split()))
r = n - arr[0]
p = 1
c = -1
for i in range(n):
    if p == 1:
        t = (arr[i] + r) % n        
    else:
        t = (n - (r - arr[i])) % n
    p = -p
    if t > c:
        c = t 
    else:
        print('No')
        break
else:
    print('Yes')
        


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

N = int(input())
G = list(map(int,input().split()))
real = [i for i in range(N)]
d = [1,-1]

if G == real:
    print('Yes')
else:
    for i in range(N):
        for j in range(N):
            G[j] = real[(G[j] + d[j%2])%N]
        if G == real:
            print('Yes')
            break
    else:
        print('No')


n = input();
li = input();
n = int(n)
li = li.split()
valid = "Yes"
for i in range(0, n - 1):
    if (int(li[i]) + int(li[i + 1]) - 2 * i - 1) % n:
        valid = "No"
        break
print(valid)


n = int(input())
l = [int(i) for i in input().split()]
d = (n - l[0]) % n
for i in range(1, n):
    r = n
    if i & 1 == 0:
        if i >= l[i]:
            r = i - l[i]
        else:
            r = i - l[i] + n
    else:
        if i <= l[i]:
            r = l[i] - i
        else:
            r = l[i] - i + n
    if r != d:
        print("No")
        d = -1
        break
if d >= 0:
    print("Yes")
    
    


n = int(input())
a = list(map(int, input().split()))
z = [i for i in range(n)]
t = a[0] - 0

for i, v in enumerate(a):
    v += t if i % 2 else -t
    if v < 0:
        v += n
    elif v >= n:
        v -= n
    a[i] = v

print('Yes' if a == z else 'No')



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

good = True

b = (n - a[0]) % n

for i in range(n):
    if i % 2 == 0:
        if (n + i - a[i]) % n != b:
            good = False
    else:
        if (a[i] - i + n) % n != b:
            good = False

if good:
    print("Yes")
else:
    print("No")




def changeGear(x,i,n):
	if(i&1 == 0):
		if(x != n-1):
			return x + 1
		else:
			return 0
	else:
		if(x == 0):
			return n-1
		else:
			return x - 1

n = int(input())

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

b = []
c = []

for i in range(n):
	b.append(i)
	c.append(a[i])

if(a == b):
	print('Yes')
	return
else:
	for i in range(n):
		a[i] = changeGear(a[i],i,n)
#print(a)

while(a != b and a != c):
	for i in range(n):
		a[i] = changeGear(a[i],i,n)
	#print(a)

if(a == b):
	print('Yes')
else:
	print('No')


def inp(s):
    j = 0
    a = []
    for i in range(len(s)):
        if s[i] == " ":
            a.append(int(s[j:i]))
            j = i+1
        if i == len(s)-1:
            a.append(int(s[j:]))
    return a

def chk(a):
    f = 0
    for i in range(len(a)):
        if a[i] != i:
            f = 1
            break
    return f


n = int(input())
s = input()
a = inp(s)
x = a
for i in range(n):
    f = 0
    if chk(a) == 0:
        f = 1
        break
    for i in range(len(a)):
        if i%2 == 0:
            a[i] = (a[i]-1)%n
        else:
            a[i] = (a[i]+1)%n

if f == 1:
    print ("Yes")
else:
    print ("No")
        













n = int(input())

z = [int(x) for x in input().split()]
w = []

for i in range(n):
    if i % 2 == 0:
        if z[i] <= i:
            w.append(i - z[i])
        else:
            w.append(n - z[i] + i)
    else:
        if i <= z[i]:
            w.append(z[i] - i)
        else:
            w.append(z[i] + n - i)

for i in range(n - 1):
    if w[i] != w[i+1]:
        print('No')
        return

print('Yes')