A remote island chain contains n islands, labeled 1 through n. Bidirectional bridges connect the islands to form a simple cycle — a bridge connects islands 1 and 2, islands 2 and 3, and so on, and additionally a bridge connects islands n and 1. The center of each island contains an identical pedestal, and all but one of the islands has a fragile, uniquely colored statue currently held on the pedestal. The remaining island holds only an empty pedestal.

The islanders want to rearrange the statues in a new order. To do this, they repeat the following process: First, they choose an island directly adjacent to the island containing an empty pedestal. Then, they painstakingly carry the statue on this island across the adjoining bridge and place it on the empty pedestal.

Determine if it is possible for the islanders to arrange the statues in the desired order.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 200 000) — the total number of islands.

The second line contains n space-separated integers a_{i} (0 ≤ a_{i} ≤ n - 1) — the statue currently placed on the i-th island. If a_{i} = 0, then the island has no statue. It is guaranteed that the a_{i} are distinct.

The third line contains n space-separated integers b_{i} (0 ≤ b_{i} ≤ n - 1) — the desired statues of the ith island. Once again, b_{i} = 0 indicates the island desires no statue. It is guaranteed that the b_{i} are distinct.


-----Output-----

Print "YES" (without quotes) if the rearrangement can be done in the existing network, and "NO" otherwise.


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

Output
YES

Input
2
1 0
0 1

Output
YES

Input
4
1 2 3 0
0 3 2 1

Output
NO



-----Note-----

In the first sample, the islanders can first move statue 1 from island 1 to island 2, then move statue 2 from island 3 to island 1, and finally move statue 1 from island 2 to island 3.

In the second sample, the islanders can simply move statue 1 from island 1 to island 2.

In the third sample, no sequence of movements results in the desired position.

Difficulty: EASY
Tags: Implementation

Constructive algorithms

Starter code:

Solutions:
input()
l1 = [int(x) for x in input().split() if x != '0']
l2 = [int(x) for x in input().split() if x != '0']
m = len(l1)
x = l1.index(l2[0])
b = True
for i in range(len(l1)):
	b &= l2[i] == l1[(x + i) % m]
print('YES' if b else 'NO')


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.remove(0)
b.remove(0)
i = a.index(b[0])
if a[i:] + a[:i] == b:
	print('YES')
else:
	print('NO')


n = int(input())
a = input().split()
b = input().split()
a.remove('0')
b.remove('0')
k = a.index(b[0])
a = a[k:] + a[:k]
if a == b:
	print('YES')
else:
	print('NO')


n = int(input()) - 1
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.remove(0)
b.remove(0)
ret = True
a_i = a.index(1)
b_i = b.index(1)
for i in range(n):
	if a[(a_i + i) % n] != b[(b_i + i) % n]:
		ret = False
		break
if ret:
	print('YES')
else:
	print('NO')


from sys import stdin
a = int(stdin.readline())
b = input().replace(' ', '').replace('0', '')
c = input().replace(' ', '').replace('0', '')
if b in 2 * c:
	print('YES')
else:
	print('NO')


def run():
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	i = a.index(1)
	j = b.index(1)
	ok = True
	cont = 0
	while cont < n:
		if a[i] != b[j]:
			ok = False
			break
		i = (i + 1) % n
		j = (j + 1) % n
		if a[i] == 0:
			i = (i + 1) % n
		if b[j] == 0:
			j = (j + 1) % n
		cont += 1
	print('YES' if ok else 'NO')

def __starting_point():
	run()
__starting_point()


from collections import deque
n = int(input()) - 1
a = list(filter(lambda x: x != 0, map(int, input().split())))
b = list(filter(lambda x: x != 0, map(int, input().split())))
lom = b.index(a[0])
if a[:n - lom] == b[lom:] and a[n - lom:] == b[:lom]:
	print('YES')
else:
	print('NO')


n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
if a[0] != 0:
	index_b = b.index(a[0])
else:
	index_b = b.index(a[1])
for index_a in range(0, len(a)):
	if a[index_a] == 0:
		continue
	if b[index_b % len(a)] == 0:
		index_b += 1
	if a[index_a] != b[index_b % len(a)]:
		print('NO')
		exit()
	index_b += 1
print('YES')


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.remove(0)
b.remove(0)
print(('NO', 'YES')[''.join(map(str, b)) in ''.join(map(str, a + a))])


readInts = lambda : list(map(int, input().split()))
n = int(input())
a = readInts()
a.remove(0)
b = readInts()
b.remove(0)
pos = a.index(b[0])
a = a[pos:] + a[:pos]
print('YES' if a == b else 'NO')


input()
f = lambda : (' ' + input()).replace(' 0', '')
(a, b) = (f(), f())
print('YES' if a in b + b else 'NO')


def main():
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	print(solver(a, b))

def solver(a, b):
	a.remove(0)
	b.remove(0)
	index = b.index(a[0])
	if b[index:] + b[:index] == a:
		return 'YES'
	else:
		return 'NO'
main()


def main():
	number_islands = int(input())
	current_order = tuple(map(int, input().split()))
	desired_order = tuple(map(int, input().split()))
	print('YES' if rotation_of(current_order, desired_order) else 'NO')

def rotation_of(seq1, seq2):
	if len(seq1) != len(seq2):
		return False
	elif len(seq1) == 0:
		return True
	seq1 = list(seq1)
	seq2 = list(seq2)
	seq1.remove(0)
	seq2.remove(0)
	seq1 = ''.join((str(_) for _ in seq1))
	seq2 = ''.join((str(_) for _ in seq2))
	return seq2 in seq1 + seq1
main()


import math, re, sys, string, operator, functools, fractions, collections
sys.setrecursionlimit(10 ** 7)
RI = lambda x=' ': list(map(int, input().split(x)))
RS = lambda x=' ': input().rstrip().split(x)
dX = [-1, 1, 0, 0, -1, 1, -1, 1]
dY = [0, 0, -1, 1, 1, -1, -1, 1]
mod = int(1000000000.0 + 7)
eps = 1e-06
pi = math.acos(-1.0)
MAX = 200010
n = RI()[0]
a = RI()
b = RI()
a = [i for i in a if i]
b = [i for i in b if i]
if len(a) != len(b) or (len(a) == n and a != b):
	print('NO')
	sys.exit(0)
ID = [0] * MAX
for i in range(len(a)):
	ID[a[i]] = (a[i - 1], a[(i + 1) % len(a)])
for i in range(len(b)):
	if ID[b[i]] != (b[i - 1], b[(i + 1) % len(b)]):
		print('NO')
		sys.exit(0)
print('YES')


n = int(input())
l1 = list(map(int, input().split()))
l2 = list(map(int, input().split()))
for k in range(n):
	if l1[k] == 0:
		l1 = l1[:k] + l1[k + 1:]
		break
for k in range(n):
	if l2[k] == 0:
		l2 = l2[:k] + l2[k + 1:]
		break
i = 0
j = 0
ans = True
for k in range(n - 1):
	if l1[k] == 1:
		i = k
	if l2[k] == 1:
		j = k
for k in range(n - 1):
	if l1[(i + k) % (n - 1)] != l2[(j + k) % (n - 1)]:
		ans = False
		break
if ans:
	print('YES')
else:
	print('NO')


x = int(input())
if x == 2:
	print('YES')
	quit()
y = list(map(int, input().split(' ')))
z = list(map(int, input().split(' ')))
kq = [i for i in y if i != 0]
jl = [i for i in z if i != 0]
o = [0] * 200001
p = [0] * 200001
t = []
for i in range(len(kq)):
	o[kq[i]] = i + 1
for i in range(len(jl)):
	p[jl[i]] = i + 1
for i in range(1, x):
	t.append((p[i] - o[i]) % (x - 1))
if t.count(t[0]) == len(t):
	print('YES')
else:
	print('NO')


n = int(input())
before = list(map(int, input().split()))
after = list(map(int, input().split()))
before.pop(before.index(0))
after.pop(after.index(0))
index = after.index(before[-1])
n -= 1
for i in range(1, n):
	if after[(index - i + 1) % n] != before[-i % n]:
		print('No')
		break
else:
	print('Yes')


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l2 = []
l1 = []
i = 0
ind = a.index(0)
while ind != n:
	l1.append(a[ind])
	ind = ind + 1
while len(l1) != n:
	l1.append(a[i])
	i += 1
i = 0
l3 = []
ind = b.index(0)
while ind != n:
	l3.append(b[ind])
	ind = ind + 1
while len(l3) != n:
	l3.append(b[i])
	i += 1
i = 0
ind = l3.index(l1[1])
while ind != n:
	l2.append(l3[ind])
	ind = ind + 1
while len(l2) != n - 1:
	if l3[i] != 0:
		l2.append(l3[i])
	i += 1
if l1[1:] == l2:
	print('YES')
else:
	print('NO')


from collections import deque
input()
a = deque()
b = deque()
temp = map(int, input().split(' '))
for i in temp:
	if i > 0:
		a.append(i)
temp = map(int, input().split(' '))
for i in temp:
	if i > 0:
		b.append(i)
while a[0] != b[0]:
	a.appendleft(a.pop())
if a == b:
	print('YES')
else:
	print('NO')


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.remove(0)
b.remove(0)
pos = a.index(b[0])
col = 0
f = True
for i in range(n - 1):
	if a[pos] != b[col]:
		f = False
		break
	else:
		col += 1
		pos = (pos + 1) % (n - 1)
if f:
	print('YES')
else:
	print('NO')


import sys
n = int(input())
a = []
b = []
x = map(int, input().split())
for i in x:
	if i > 0:
		a.append(i)
x = map(int, input().split())
for i in x:
	if i > 0:
		b.append(i)
n = n - 1
for i in range(0, n):
	if b[i] == a[0]:
		for j in range(0, n):
			if a[j] != b[(i + j) % n]:
				print('NO')
				return
		break
print('YES')


import sys
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
st = set()
idx = 0
i = 0
j = 0
while i < n and a[i] == 0:
	i += 1
while j < n and a[i] != b[j]:
	j += 1
b = b[j:] + b[:j]
j = 0
while i < n:
	if a[i] != 0:
		while j < n and b[j] == 0:
			j += 1
		if b[j] != a[i] or j == n:
			print('NO')
			return
		j += 1
	i += 1
print('YES')


n = int(input())
res = True
l = list(map(int, input().split()))
m = list(map(int, input().split()))
l.remove(0)
m.remove(0)
t = m.index(l[0])
for i in range(n - 1):
	if l[i] != m[(i + t) % (n - 1)]:
		res = False
if res:
	print('YES')
else:
	print('NO')


import io
import sys
import time
import random
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

def normalize(a):
	zeropos = a.index(0)
	del a[zeropos]
	ret = a[:]
	n = len(a)
	count = 0
	zeropos = a.index(1)
	for i in range(zeropos, n):
		ret[count] = a[i]
		count += 1
	for i in range(0, zeropos):
		ret[count + i] = a[i]
	return ret
print('YES' if normalize(a) == normalize(b) else 'NO')


n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
x = A.index(1)
y = B.index(1)
z = 0
for i in range(n):
	x += A[(x + i) % n] == 0
	y += B[(y + i) % n] == 0
	z += A[(x + i) % n] == B[(y + i) % n]
if z == n:
	print('YES')
else:
	print('NO')


class CodeforcesTask635BSolution:

	def __init__(self):
		self.result = ''
		self.n = 0
		self.curr = []
		self.need = []

	def read_input(self):
		self.n = int(input()) - 1
		self.curr = [int(x) for x in input().split(' ') if int(x)]
		self.need = [int(x) for x in input().split(' ') if int(x)]

	def process_task(self):
		neighbours1 = {}
		neighbours2 = {}
		for x in range(self.n - 1):
			neighbours1[str(self.curr[x])] = (self.curr[x - 1], self.curr[x + 1])
			neighbours2[str(self.need[x])] = (self.need[x - 1], self.need[x + 1])
		neighbours1[str(self.curr[self.n - 1])] = (self.curr[self.n - 2], self.curr[0])
		neighbours2[str(self.need[self.n - 1])] = (self.need[self.n - 2], self.need[0])
		canbe = True
		for p in self.curr:
			if neighbours1[str(p)] != neighbours2[str(p)]:
				canbe = False
				break
		self.result = 'YES' if canbe else 'NO'

	def get_result(self):
		return self.result
Solution = CodeforcesTask635BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


def main():
	input()
	aa = input().split()
	bb = input().split()
	aa.remove('0')
	bb.remove('0')
	a = aa.index('1')
	b = bb.index('1')
	print(('NO', 'YES')[aa[a:] + aa[:a] == bb[b:] + bb[:b]])

def __starting_point():
	main()
__starting_point()


read = lambda : map(int, input().split())
n = int(input())
a = list(read())
b = list(read())
(A, B) = ([], [])
i = a.index(1)
while len(A) < n:
	if a[i]:
		A.append(a[i])
	i = (i + 1) % n
i = b.index(1)
while len(B) < n:
	if b[i]:
		B.append(b[i])
	i = (i + 1) % n
ans = 'YES' if A == B else 'NO'
print(ans)


n = int(input())
per = list(map(int, input().split()))
per2 = list(map(int, input().split()))
per.pop(per.index(0))
per2.pop(per2.index(0))
cou = 0
ans = 0
for j in range(n - 1):
	if per[0] == per2[j]:
		cou = j
		break
for i in range(n - 1):
	if per[i] != per2[cou]:
		ans = 1
		break
	elif cou < n - 2:
		cou += 1
	else:
		cou = 0
if ans == 0:
	print('YES')
else:
	print('NO')


n = int(input())
a = list(map(int, input().strip().split(' ')))
b = list(map(int, input().strip().split(' ')))
if n == 2 or n == 3:
	print('YES')
else:
	del a[a.index(0)]
	del b[b.index(0)]
	p1 = a[0]
	c = []
	ind = b.index(p1)
	c = b[ind:] + b[:ind]
	if c == a:
		print('YES')
	else:
		print('NO')


n = int(input())
a = [int(x) for x in input().split() if x != '0']
b = [int(x) for x in input().split() if x != '0']
for i in range(0, len(b)):
	if b[i] == a[0]:
		break
result = True
k = 0
for j in range(i, len(b)):
	if b[j] != a[k]:
		result = False
		break
	k += 1
if result:
	for j in range(0, i):
		if b[j] != a[k]:
			result = False
			break
		k += 1
if result:
	print('YES')
else:
	print('NO')


n = int(input())
ps = list(map(int, input().split()))
qs = list(map(int, input().split()))
ps.remove(0)
qs.remove(0)
i = qs.index(ps[0])
if ps == qs[i:] + qs[:i]:
	print('YES')
else:
	print('NO')


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A.remove(0)
B.remove(0)
ind_b = B.index(A[0])
R = B[ind_b:] + B[0:ind_b]
if A == R:
	print('YES')
else:
	print('NO')


from bisect import bisect
n = int(input())
statues = [int(x) for x in input().split()]
new_statues = [int(x) for x in input().split()]
statues.remove(0)
new_statues.remove(0)
shift = new_statues.index(1) - statues.index(1)
print('YES' if all((statues[i] == new_statues[(i + shift) % (n - 1)] for i in range(n - 1))) else 'NO')


no_islands = int(input())
initial = input().split()
final = input().split()
initial.remove('0')
final.remove('0')
first = initial.index(final[0])
if initial[first:] + initial[:first] == final:
	print('YES')
else:
	print('NO')


n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
L = []
e = A.index(1)
for i in range(n):
	if A[e] > 0:
		L += [A[e]]
	e += 1
	if e == n:
		e = 0
L2 = []
e = B.index(1)
for i in range(n):
	if B[e] > 0:
		L2 += [B[e]]
	e += 1
	if e == n:
		e = 0
if L == L2:
	print('YES')
else:
	print('NO')


read = lambda : map(int, input().split())
n = int(input())
a = list(read())
b = list(read())
(A, B) = ([], [])
i = k = 0
while a[i] != 1:
	i += 1
while k < n:
	if a[i]:
		A.append(a[i])
	i = (i + 1) % n
	k += 1
i = k = 0
while b[i] != 1:
	i += 1
while k < n:
	if b[i]:
		B.append(b[i])
	i = (i + 1) % n
	k += 1
ans = 'YES' if A == B else 'NO'
print(ans)


import time
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
start = time.time()
z = a.index(0)
a = a[0:z] + a[z + 1:]
z = b.index(0)
b = b[0:z] + b[z + 1:]
z = b.index(a[0])
b = b[z:] + b[:z]
ans = 'YES'
for i in range(n - 1):
	if a[i] != b[i]:
		ans = 'NO'
		break
print(ans)
finish = time.time()


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
i = 0
t = 0 if a[0] != 0 else 1
for j in range(n):
	if a[t] == b[j]:
		i = j
		break
bl = True
for j in range(n):
	if b[i % n] != a[j]:
		if a[j] == 0:
			continue
		elif b[i % n] == 0 and b[(i + 1) % n] == a[j]:
			i += 2
			continue
		bl = False
		break
	i += 1
print('YES' if bl else 'NO')


n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
fl = True
for i in range(n):
	if a[i] == 0:
		a.pop(i)
		break
for i in range(n):
	if b[i] == 0:
		b.pop(i)
		break
for i in range(n):
	if b[i] == a[0]:
		c = i
		break
for i in range(c + 1, n - 1):
	if b[i] != a[i - c]:
		fl = False
for i in range(c):
	if b[i] != a[n - c + i - 1]:
		fl = False
if fl:
	print('YES')
else:
	print('NO')


n = int(input())
start = [x for x in input().split(' ') if not x == '0']
end = [x for x in input().split(' ') if not x == '0']
index1 = start.index('1')
index2 = end.index('1')
for i in range(n - 1):
	if not start[index1] == end[index2]:
		print('NO')
		break
	index1 = (index1 + 1) % (n - 1)
	index2 = (index2 + 1) % (n - 1)
else:
	print('YES')


n = int(input())
s1 = input().split()
s2 = input().split()
st1 = 0
st2 = 0
for i in range(n):
	if s1[i] == '1':
		st1 = i
	if s2[i] == '1':
		st2 = i
i = (st1 + 1) % n
j = (st2 + 1) % n
f = True
steps = 0
while steps < n:
	if s1[i] == '0':
		i = (i + 1) % n
	if s2[j] == '0':
		j = (j + 1) % n
	if s1[i] != s2[j]:
		f = False
		break
	i = (i + 1) % n
	j = (j + 1) % n
	steps += 1
if f:
	print('YES')
else:
	print('NO')


n = int(input())
a = list(map(int, input().split()))
a.remove(0)
b = list(map(int, input().split()))
b.remove(0)
start = b.index(a[0])
for i in range(n - 1):
	if a[i] != b[(i + start) % (n - 1)]:
		print('NO')
		exit(0)
print('YES')


n = int(input())
s1 = list(input().strip().split())
s2 = list(input().strip().split())
s1.remove('0')
s2.remove('0')
s1 = ''.join(s1)
s2 = ''.join(s2)
s1 = s1 + s1
if s2 in s1:
	print('YES')
else:
	print('NO')