There is an array $a$ of length $n$. You may perform the following operation any number of times:

Choose two indices $l$ and $r$ where $1 \le l < r \le n$ and $a_l = a_r$. Then, set $a[l \ldots r] = [a_{l+1}, a_{l+2}, \ldots, a_r, a_l]$.

You are also given another array $b$ of length $n$ which is a permutation of $a$. Determine whether it is possible to transform array $a$ into an array $b$ using the above operation some number of times.


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 2 \cdot 10 ^ 5$)  — the length of array $a$ and $b$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$)  — elements of the array $a$.

The third line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le n$)  — elements of the array $b$.

It is guaranteed that $b$ is a permutation of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10 ^ 5$


-----Output-----

For each test case, print "YES" (without quotes) if it is possible to transform array $a$ to $b$, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).


-----Examples-----

Input
5
5
1 2 3 3 2
1 3 3 2 2
5
1 2 4 2 1
4 2 2 1 1
5
2 4 5 5 2
2 2 4 5 5
3
1 2 3
1 2 3
3
1 1 2
2 1 1
Output
YES
YES
NO
YES
NO


-----Note-----

In the first test case, we can choose $l=2$ and $r=5$ to form $[1, 3, 3, 2, 2]$.

In the second test case, we can choose $l=2$ and $r=4$ to form $[1, 4, 2, 2, 1]$. Then, we can choose $l=1$ and $r=5$ to form $[4, 2, 2, 1, 1]$.

In the third test case, it can be proven that it is not possible to transform array $a$ to $b$ using the operation.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Amortized analysis

Implementation

Constructive algorithms


Solutions:
import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	b = list(map(int, inp().split()))
	w = [0] * (n + 1)
	j = 0
	for i in range(n):
		x = b[i]
		while j < n and a[j] != x:
			w[a[j]] += 1
			j += 1
		if j == n:
			print('NO')
			return
		if i + 1 < n and b[i + 1] == x:
			if j + 1 >= n or a[j + 1] != x:
				if w[x] > 0:
					w[x] -= 1
					i += 1
					continue
		j += 1
	print('YES')

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


def ss(a, b):
	d = {}
	n = len(a)
	i = n - 1
	j = n - 1
	if a[-1] != b[-1]:
		return 'NO'
	while i >= 0 and j >= 0:
		if a[i] == b[j]:
			i -= 1
			j -= 1
			continue
		if b[j] == b[j + 1]:
			x = b[j]
			if x in d:
				d[x] += 1
			else:
				d[x] = 1
			j -= 1
			continue
		x = a[i]
		if x in d and d[x] > 0:
			d[x] -= 1
			i -= 1
		else:
			return 'NO'
	return 'YES'
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(ss(a, b))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = {}
	j = n - 1
	k = n - 1
	e = 0
	while j >= 0 and k >= 0:
		if b[j] == a[k]:
			k = k - 1
			j = j - 1
		elif j < n - 1:
			if b[j] == b[j + 1]:
				if b[j] in d:
					d[b[j]] = d[b[j]] + 1
					j = j - 1
				else:
					d[b[j]] = 1
					j = j - 1
			elif a[k] in d:
				if d[a[k]] > 0:
					d[a[k]] = d[a[k]] - 1
					k = k - 1
				else:
					e = 1
					print('NO')
					break
			else:
				e = 1
				print('NO')
				break
		else:
			e = 1
			print('NO')
			break
	if e == 0:
		print('YES')


import collections

def transform(a, b):
	counter = collections.Counter()
	while a:
		while len(b) > 1 and b[-1] == b[-2]:
			counter[b.pop()] += 1
		if b and a[-1] == b[-1]:
			a.pop()
			b.pop()
		elif counter[a[-1]]:
			counter[a.pop()] -= 1
		else:
			return False
	return True
for _ in range(int(input())):
	input()
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print('YES' if transform(a, b) else 'NO')


tc = int(input())
for _ in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	if n == 1:
		print('YES')
		continue
	check = [0 for _ in range(n + 1)]
	(i1, i2) = (0, 0)
	while i1 < n and i2 < n:
		if a[i1] != b[i2]:
			if check[b[i2]] > 0 and a[i1 - 1] == b[i2]:
				check[b[i2]] -= 1
				i2 += 1
			else:
				check[a[i1]] += 1
				i1 += 1
		else:
			i1 += 1
			i2 += 1
	while i2 < n and check[b[i2]] > 0 and (a[i1 - 1] == b[i2]):
		check[b[i2]] -= 1
		i2 += 1
	if any(check):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	(a, b) = ([*map(int, input().split())], [*map(int, input().split())])
	d = {}
	(x, i, last) = (n - 1, n - 1, 0)
	while i > 0:
		if b[i] == a[x]:
			x -= 1
			last = b[i]
			i -= 1
		elif b[i] == last:
			d[b[i]] = d.get(b[i], 0) + 1
			last = b[i]
			i -= 1
		elif d.get(a[x], 0) > 0:
			d[a[x]] -= 1
			x -= 1
		else:
			print('NO')
			break
	else:
		print('YES')


for case in range(int(input())):
	n = int(input())
	a = [int(j) for j in input().split()]
	b = [int(j) for j in input().split()]
	carry = {}
	try:
		i = 0
		for j in range(n):
			while a[i] != b[j]:
				carry[a[i]] = carry.get(a[i], 0) + 1
				i += 1
			if carry.get(a[i], 0) == 0:
				i += 1
			else:
				carry[a[i]] -= 1
	except:
		i = n + 1
	print(['NO', 'YES'][i == n])


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	if n == 1:
		print('YES')
		continue
	s = [0 for i in range(max(a) + 1)]
	i = n - 1
	j = n - 1
	flag = True
	while i >= 0 and j >= 0:
		while j >= 0 and b[j] == b[j - 1]:
			s[b[j]] += 1
			j -= 1
		if a[i] == b[j]:
			i -= 1
			j -= 1
		elif s[a[i]] == 0:
			flag = False
			break
		else:
			s[a[i]] -= 1
			i -= 1
	if flag:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline
rounds = int(input())
for ii in range(rounds):
	out = 'YES'
	length = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	seen = {}
	ind1 = length - 1
	ind2 = length - 1
	while ind1 >= 0 and ind2 >= 0:
		if ind2 > 0 and arr2[ind2] == arr2[ind2 - 1]:
			ind2 -= 1
			if arr2[ind2] in seen:
				seen[arr2[ind2]] += 1
			else:
				seen[arr2[ind2]] = 1
		elif arr1[ind1] == arr2[ind2]:
			ind1 -= 1
			ind2 -= 1
		elif arr1[ind1] in seen and seen[arr1[ind1]] > 0:
			seen[arr1[ind1]] -= 1
			ind1 -= 1
		else:
			out = 'NO'
			break
	print(out)


from collections import defaultdict

class multiset:

	def __init__(self):
		self.multiset = defaultdict(int)

	def add(self, key):
		self.multiset[key] += 1

	def remove(self, key):
		if key in self.multiset:
			self.multiset[key] -= 1
			if self.multiset[key] == 0:
				del self.multiset[key]

	def __contains__(self, val):
		return self.multiset[val] > 0

	def __len__(self):
		return sum(self.multiset.values())

	def __str__(self):
		return '< ' + ''.join([(str(i) + ' ') * self.multiset[i] for i in self.multiset]) + '>'
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	mset = multiset()
	(i, j) = (n - 1, n - 1)
	ans = 'YES'
	while i >= 0 and j >= 0:
		while j > 0 and B[j] == B[j - 1]:
			mset.add(B[j])
			j -= 1
		if A[i] == B[j]:
			i -= 1
			j -= 1
		elif A[i] in mset:
			mset.remove(A[i])
			i -= 1
		else:
			ans = 'NO'
			break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = []
	d = []
	for i in a:
		if len(c) == 0:
			c.append([i, 1])
		elif i == c[-1][0]:
			c[-1][1] += 1
		else:
			c.append([i, 1])
	for i in b:
		if len(d) == 0:
			d.append([i, 1])
		elif i == d[-1][0]:
			d[-1][1] += 1
		else:
			d.append([i, 1])
	a = c[:]
	b = d[:]
	cur = dict()
	i = 0
	j = 0
	while i < len(a) or j < len(b):
		if i == len(a) or j == len(b):
			print('NO')
			break
		if a[i][0] == b[j][0]:
			v1 = a[i][1] + cur.get(a[i][0], 0)
			v2 = b[j][1]
			if v1 < v2:
				cur[a[i][0]] = v1
				i += 1
				continue
			cur[a[i][0]] = v1 - v2
			i += 1
			j += 1
		else:
			cur[a[i][0]] = cur.get(a[i][0], 0) + a[i][1]
			i += 1
	else:
		print('YES')