← 返回题目列表

Codeforces · 2197/B

B. 数组和排列

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

给定一个长度为 $$$n$$$$$$^{\text{∗}}$$$ 的排列 $$$p$$$ 和一个长度为 $$$n$$$ 的数组 $$$a$$$。

我们称排列 $$$p$$$ 生成 对于数组 $$$a$$$,如果数组 $$$a$$$ 可以通过应用以下类型的一些操作(可能为零)从排列 $$$p$$$ 获得:

选择一个索引 $$$i$$$ ($$$1 \le i \lt n$$$) 并执行以下两种替换之一:

  • $$$p_{i} := p_{i + 1}$$$;
  • $$$p_{i + 1} := p_{i}$$$。

换句话说,在一次操作中,您可以选择数组中两个相邻的元素,并将其中一个元素的值复制到另一个元素中。

您需要报告排列 $$$p$$$ 是否为 生成 为数组 $$$a$$$。

$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

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

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

每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_{i} \le n$$$) — 排列的元素。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_{i} \le n$$$) — 数组的元素。

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

输出

对于每个测试用例,输出“是" 如果排列 $$$p$$$ 是 生成 为数组 $$$a$$$,否则输出 "NO".

您可以以任何大小写(小写或大写)输出每个字母。例如,字符串“是", "是", "是“,和”是”将被接受为肯定答案。

示例

输入
复制

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

输出
复制

YES
NO
YES
NO
YES
YES

注意

在第一个测试用例中,数组是使用一个操作从排列生成的:

  • $$$i = 2$$$ 和 $$$p_{i + 1} := p_{i}$$$。

在第二个测试用例中,不可能从$$$p$$$获得$$$a$$$。

在第三个测试用例中,需要执行$$$2$$$操作:

  • $$$i = 1$$$ 和 $$$p_{i} := p_{i + 1}$$$;
  • $$$i = 2$$$ 和 $$$p_{i + 1} := p_{i}$$$。