← 返回题目列表

Codeforces · 1672/D

D. 循环旋转

中文机器翻译题面 查看原题

有一个长度为$$$n$$$的数组$$$a$$$。您可以多次执行以下操作:

- 选择两个索引 $$$l$$$ 和 $$$r$$$,其中 $$$1 \le l < r \le n$$$ 和 $$$a_l = a_r$$$。然后,设置 $$$a[l \ldots r] = [a_{l+1}, a_{l+2}, \ldots, a_r, a_l]$$$。

您还获得了另一个长度为 $$$n$$$ 的数组 $$$b$$$,它是 $$$a$$$ 的排列。确定是否可以使用上述操作多次将数组 $$$a$$$ 转换为数组 $$$b$$$。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10 ^ 5$$$) — 数组 $$$a$$$ 和 $$$b$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — 数组 $$$a$$$ 的元素。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) — 数组 $$$b$$$ 的元素。

保证 $$$b$$$ 是 $$$a$$$ 的排列。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10 ^ 5$$$

输出

对于每个测试用例,如果可以将数组 $$$a$$$ 转换为 $$$b$$$,则打印“YES”(不带引号),否则打印“NO”(不带引号)。

在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”和“Yes”将被识别为肯定响应)。

示例

输入 #1

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

输出 #1

YES
YES
NO
YES
NO

注意

在第一个测试用例中,我们可以选择 $$$l=2$$$ 和 $$$r=5$$$ 组成 $$$[1, 3, 3, 2, 2]$$$。

在第二个测试用例中,我们可以选择 $$$l=2$$$ 和 $$$r=4$$$ 来组成 $$$[1, 4, 2, 2, 1]$$$。然后,我们可以选择$$$l=1$$$和$$$r=5$$$来组成$$$[4,2,2,1,1]$$$。

在第三个测试用例中,可以证明不可能使用该操作将数组 $$$a$$$ 转换为 $$$b$$$。