You are given an array a_1, a_2, ..., a_n and an array b_1, b_2, ..., b_n.

For one operation you can sort in non-decreasing order any subarray a[l ... r] of the array a.

For example, if a = [4, 2, 2, 1, 3, 1] and you choose subbarray a[2 ... 5], then the array turns into [4, 1, 2, 2, 3, 1]. 

You are asked to determine whether it is possible to obtain the array b by applying this operation any number of times (possibly zero) to the array a.

Input

The first line contains one integer t (1 ≤ t ≤ 3 ⋅ 10^5) — the number of queries.

The first line of each query contains one integer n (1 ≤ n ≤ 3 ⋅ 10^5).

The second line of each query contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n).

The third line of each query contains n integers b_1, b_2, ..., b_n (1 ≤ b_i ≤ n).

It is guaranteed that ∑ n ≤ 3 ⋅ 10^5 over all queries in a test.

Output

For each query print YES (in any letter case) if it is possible to obtain an array b and NO (in any letter case) otherwise.

Example

Input


4
7
1 7 1 4 4 5 6
1 1 4 4 5 7 6
5
1 1 3 3 5
1 1 3 3 5
2
1 1
1 2
3
1 2 3
3 2 1


Output


YES
YES
NO
NO

Note

In first test case the can sort subarray a_1 ... a_5, then a will turn into [1, 1, 4, 4, 7, 5, 6], and then sort subarray a_5 ... a_6.

Difficulty: VERY_HARD
Tags: Sorting

Data structures
Skill types: Sorting

Data structures

Starter code:

Solutions:
from sys import stdin, stdout
from collections import defaultdict
t = int(stdin.readline())
inf = 10 ** 6

def merge_sort(order, a):
	if len(order) == 1:
		return (order, a)
	mid = (len(order) + 1) // 2
	(left_o, left_a) = merge_sort(order[:mid], a[:mid])
	(right_o, right_a) = merge_sort(order[mid:], a[mid:])
	l_mins = []
	cur_min = inf
	for i in range(mid - 1, -1, -1):
		cur_min = min(cur_min, left_a[i])
		l_mins.append(cur_min)
	l_mins.reverse()
	l_idx = 0
	r_idx = 0
	o_ans = []
	a_ans = []
	while l_idx < mid and r_idx < len(order) - mid:
		if left_o[l_idx] < right_o[r_idx]:
			o_ans.append(left_o[l_idx])
			a_ans.append(left_a[l_idx])
			l_idx += 1
		else:
			if right_a[r_idx] > l_mins[l_idx]:
				raise Exception
			o_ans.append(right_o[r_idx])
			a_ans.append(right_a[r_idx])
			r_idx += 1
	while l_idx < mid:
		o_ans.append(left_o[l_idx])
		a_ans.append(left_a[l_idx])
		l_idx += 1
	while r_idx < len(order) - mid:
		o_ans.append(right_o[r_idx])
		a_ans.append(right_a[r_idx])
		r_idx += 1
	return (o_ans, a_ans)

def process():
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	b = list(map(int, stdin.readline().split()))
	order = [0] * n
	occurrences = defaultdict(list)
	for (i, num) in enumerate(b):
		occurrences[num].append(i)
	for i in range(n - 1, -1, -1):
		x = a[i]
		if len(occurrences[x]) == 0:
			stdout.write('NO\n')
			return
		order[i] = occurrences[x].pop()
	try:
		merge_sort(order, a)
		stdout.write('YES\n')
	except:
		stdout.write('NO\n')
for it in range(t):
	process()


ide = 10 ** 18

def func(a, b):
	return min(a, b)

class SegmentTree:

	def __init__(self, ls, commutative=True):
		if commutative == True:
			self.n = len(ls)
			self.tree = [ide for i in range(self.n)] + ls
		else:
			self.n = 2 ** (len(ls) - 1).bit_length()
			self.tree = [ide for i in range(self.n)] + ls + [ide for i in range(self.n - len(ls))]
		for i in range(1, self.n)[::-1]:
			self.tree[i] = func(self.tree[i << 1 | 0], self.tree[i << 1 | 1])

	def getall(self):
		return self.tree[1]

	def get(self, l, r):
		lret = ide
		rret = ide
		l += self.n
		r += self.n
		while l < r:
			if l & 1:
				lret = func(lret, self.tree[l])
				l += 1
			if r & 1:
				rret = func(self.tree[r - 1], rret)
			l >>= 1
			r >>= 1
		ret = func(lret, rret)
		return ret

	def update(self, i, x):
		i += self.n
		self.tree[i] = x
		while i > 1:
			i >>= 1
			self.tree[i] = func(self.tree[i << 1 | 0], self.tree[i << 1 | 1])
import sys
input = sys.stdin.readline
from collections import Counter, defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	if Counter(a) != Counter(b):
		print('NO')
		continue
	segtree = SegmentTree(a)
	dc = defaultdict(list)
	for i in range(n)[::-1]:
		dc[a[i]].append(i)
	for i in range(n):
		x = b[i]
		aix = dc[x].pop()
		if segtree.get(0, aix + 1) == x:
			segtree.update(aix, ide)
		else:
			print('NO')
			break
	else:
		print('YES')


import sys
input = sys.stdin.readline
Q = int(input())
from collections import Counter
for testcases in range(Q):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	if Counter(A) != Counter(B):
		print('NO')
		continue
	seg_el = 1 << n.bit_length()
	SEG = [0] * (2 * seg_el)
	for i in range(n):
		SEG[i + seg_el] = A[i]
	for i in range(seg_el - 1, 0, -1):
		SEG[i] = min(SEG[i * 2], SEG[i * 2 + 1])

	def update(n, x, seg_el):
		i = n + seg_el
		SEG[i] = x
		i >>= 1
		while i != 0:
			SEG[i] = min(SEG[i * 2], SEG[i * 2 + 1])
			i >>= 1

	def getvalues(l, r):
		L = l + seg_el
		R = r + seg_el
		ANS = 1 << 30
		while L < R:
			if L & 1:
				ANS = min(ANS, SEG[L])
				L += 1
			if R & 1:
				R -= 1
				ANS = min(ANS, SEG[R])
			L >>= 1
			R >>= 1
		return ANS
	A0 = [[] for i in range(n + 1)]
	B0 = [[] for i in range(n + 1)]
	for i in range(n):
		A0[A[i]].append(i)
		B0[B[i]].append(i)
	COUNTN = [0] * (n + 1)
	for b in B:
		if getvalues(0, A0[b][COUNTN[b]]) < b:
			print('NO')
			break
		update(A0[b][COUNTN[b]], 1 << 30, seg_el)
		COUNTN[b] += 1
	else:
		print('YES')


from sys import stdin
from collections import deque

class Stree:

	def __init__(self, f, n, default, init_data):
		self.ln = 2 ** (n - 1).bit_length()
		self.data = [default] * (self.ln * 2)
		self.f = f
		self.default = default
		for (i, d) in init_data.items():
			self.data[self.ln + i] = d
		for j in range(self.ln - 1, -1, -1):
			self.data[j] = f(self.data[j * 2], self.data[j * 2 + 1])

	def update(self, i, a):
		p = self.ln + i
		self.data[p] = a
		while p > 1:
			p = p // 2
			self.data[p] = self.f(self.data[p * 2], self.data[p * 2 + 1])

	def get(self, i, j):

		def _get(l, r, p):
			if i >= r or j <= l:
				return self.default
			if i <= l and j >= r:
				return self.data[p]
			else:
				m = (l + r) // 2
				while j < m:
					r = m
					p = p * 2
					m = (l + r) // 2
				while i > m:
					r = m
					p = p * 2
					m = (l + r) // 2
				return self.f(_get(l, m, p * 2), _get(m, r, p * 2 + 1))
		return _get(0, self.ln, 1)
si = iter(stdin)
t = int(next(si))
for _ in range(t):
	n = int(next(si))
	aa = list(map(int, next(si).split()))
	bb = list(map(int, next(si).split()))
	pp = {}
	for i in range(n - 1, -1, -1):
		a = aa[i]
		if a in pp:
			pp[a].append(i)
		else:
			pp[a] = [i]
	pplast = {a: p[-1] for (a, p) in pp.items()}
	stree = Stree(min, n + 1, n + 1, pplast)
	result = 'YES'
	m = 0
	for b in bb:
		if b in pp and pp[b] != []:
			p = pp[b].pop()
			if stree.get(0, b) < p:
				result = 'NO'
				break
			if pp[b] == []:
				stree.update(b, n + 1)
			else:
				stree.update(b, pp[b][-1])
		else:
			result = 'NO'
			break
	print(result)


import sys
inp = iter(map(int, sys.stdin.read().split())).__next__

def fenwick_upd(a, i, x):
	while i < len(a):
		a[i] = max(x, a[i])
		i += i & -i

def fenwick_qry(a, i):
	r = 0
	while i > 0:
		r = max(r, a[i])
		i -= i & -i
	return r
out = []
for t in range(inp()):
	n = inp()
	a = [inp() for _ in range(n)]
	b = [inp() for _ in range(n)]
	ok = 1
	p = [[] for _ in range(n + 1)]
	for i in range(n - 1, -1, -1):
		p[b[i]].append(i)
	f = [0] * (n + 1)
	for x in a:
		if not p[x] or fenwick_qry(f, x) > p[x][-1]:
			ok = 0
			break
		fenwick_upd(f, x, p[x].pop())
	out.append('YES' if ok else 'NO')
print(*out, sep='\n')


import sys
from collections import Counter

class Segtree:

	def __init__(self, A, intv, initialize=True, segf=min):
		self.N = len(A)
		self.N0 = 2 ** (self.N - 1).bit_length()
		self.intv = intv
		self.segf = segf
		if initialize:
			self.data = [intv] * (self.N0 - 1) + A + [intv] * (self.N0 - self.N + 1)
			for i in range(self.N0 - 2, -1, -1):
				self.data[i] = self.segf(self.data[2 * i + 1], self.data[2 * i + 2])
		else:
			self.data = [intv] * (2 * self.N0)

	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k >= 0:
			k = (k - 1) // 2
			self.data[k] = self.segf(self.data[2 * k + 1], self.data[2 * k + 2])

	def query(self, l, r):
		(L, R) = (l + self.N0, r + self.N0)
		s = self.intv
		while L < R:
			if R & 1:
				R -= 1
				s = self.segf(s, self.data[R - 1])
			if L & 1:
				s = self.segf(s, self.data[L - 1])
				L += 1
			L >>= 1
			R >>= 1
		return s
T = int(input())

def solve(N, A, B):
	if Counter(A) != Counter(B):
		return False
	ctr = [0] * (N + 1)
	tableA = [[] for _ in range(N + 1)]
	for i in range(N):
		tableA[A[i]].append(i)
	bri = [None] * N
	for i in range(N):
		b = B[i]
		bri[i] = tableA[b][ctr[b]]
		ctr[b] += 1
	St = Segtree(A, 10 ** 9, True, min)
	for idx in bri:
		if A[idx] > St.query(0, idx):
			return False
		St.update(idx, 10 ** 9)
	return True
for _ in range(T):
	if solve(int(sys.stdin.readline()), list(map(int, sys.stdin.readline().split())), list(map(int, sys.stdin.readline().split()))):
		print('YES')
	else:
		print('NO')