← 返回题目列表

Codeforces · 1674/D

D. A-B-C 排序

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

给定三个数组 $$$a$$$、$$$b$$$ 和 $$$c$$$。最初,数组 $$$a$$$ 由 $$$n$$$ 元素组成,数组 $$$b$$$ 和 $$$c$$$ 为空。

您正在执行以下由两个步骤组成的算法:

- 步骤$$$1$$$:当$$$a$$$不为空时,从$$$a$$$中取出最后一个元素并将其移动到数组$$$b$$$的中间。如果$$$b$$$当前长度为奇数,则可以选择:将$$$a$$$中的元素放置到$$$b$$$中间元素的左侧或右侧。结果,$$$a$$$ 变为空,$$$b$$$ 由$$$n$$$ 元素组成。
- 步骤$$$2$$$:当$$$b$$$不为空时,从$$$b$$$中取出中间元素并将其移动到数组$$$c$$$的末尾。如果 $$$b$$$ 当前的长度为偶数,您可以选择采用两个中间元素中的哪一个。结果,$$$b$$$ 变为空,而 $$$c$$$ 现在由 $$$n$$$ 元素组成。

你能让数组 $$$c$$$ 按非降序排序吗?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。接下来的 $$$t$$$ 案例如下。

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

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) - 数组 $$$a$$$ 本身。

保证 $$$n$$$ 的总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试,如果可以使数组 $$$c$$$ 按非递减顺序排序,则打印 YES(不区分大小写)。否则,打印 NO(不区分大小写)。

示例

输入 #1

3
4
3 1 5 3
3
3 2 1
1
7331

输出 #1

YES
NO
YES

注意

在第一个测试用例中,我们可以对 $$$a = [3, 1, 5, 3]$$$ 执行以下操作:

步骤 $$$1$$$: $$$a$$$$$$[3, 1, 5, 3]$$$$$$\Rightarrow$$$$$$[3, 1, 5]$$$$$$\Rightarrow$$$$$$[3, 1]$$$$$$\右箭头$$$$$$[3]$$$$$$\右箭头$$$$$$[]$$$$$$b$$$$$$[]$$$$$$[\下划线{3}]$$$$$$[3,\下划线{5}]$$$$$$[3,\下划线{1}, 5]$$$$$$[3, \下划线{3}, 1, 5]$$$

步骤 $$$2$$$: $$$b$$$$$$[3, 3, \underline{1}, 5]$$$$$$\Rightarrow$$$$$$[3, \underline{3}, 5]$$$$$$\Rightarrow$$$$$$[\underline{3}, 5]$$$$$$\右箭头$$$$$$[\下划线{5}]$$$$$$$\右箭头$$$$$$[]$$$$$$c$$$$$$[]$$$$$$[1]$$$$$$[1, 3]$$$$$$[1, 3, 3]$$$$$$[1, 3, 3, 5]$$$ 作为结果,数组 $$$c = [1, 3, 3, 5]$$$ 并且已排序。