CF1674D.A-B-C Sort

You are given three arrays $a$, $b$ and $c$. Initially, array $a$ consists of $n$ elements, arrays $b$ and $c$ are empty.

You are performing the following algorithm that consists of two steps:

• Step $1$: while $a$ is not empty, you take the last element from $a$ and move it in the middle of array $b$. If $b$ currently has odd length, you can choose: place the element from $a$ to the left or to the right of the middle element of $b$. As a result, $a$ becomes empty and $b$ consists of $n$ elements.
• Step $2$: while $b$ is not empty, you take the middle element from $b$ and move it to the end of array $c$. If $b$ currently has even length, you can choose which of two middle elements to take. As a result, $b$ becomes empty and $c$ now consists of $n$ elements.

Refer to the Note section for examples.

Can you make array $c$ sorted in non-decreasing order?

给你三个数组 $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$ 个元素。

示例请参见“注释”（Note）部分。

你能否通过合理选择所有可选操作，使得最终得到的数组 $c$ 是非递减有序的？

The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Next $t$ cases follow.

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

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — the array $a$ itself.

It's guaranteed that the sum of $n$ doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test, print YES (case-insensitive), if you can make array $c$ sorted in non-decreasing order. Otherwise, print NO (case-insensitive).

对于每个测试用例，如果可以将数组 $c$ 变为非递减排序，则输出 YES（不区分大小写）；否则输出 NO（不区分大小写）。

In the first test case, we can do the following for $a = [3, 1, 5, 3]$:

Step $1$:

$a$

$[3, 1, 5, 3]$

$\Rightarrow$

$[3, 1, 5]$

$\Rightarrow$

$[3, 1]$

$\Rightarrow$

$[3]$

$\Rightarrow$

$[]$

$b$

$[]$

$[\underline{3}]$

$[3, \underline{5}]$

$[3, \underline{1}, 5]$

$[3, \underline{3}, 1, 5]$

Step $2$:

$b$

$[3, 3, \underline{1}, 5]$

$\Rightarrow$

$[3, \underline{3}, 5]$

$\Rightarrow$

$[\underline{3}, 5]$

$\Rightarrow$

$[\underline{5}]$

$\Rightarrow$

$[]$

$c$

$[]$

$[1]$

$[1, 3]$

$[1, 3, 3]$

$[1, 3, 3, 5]$

As a result, array $c = [1, 3, 3, 5]$ and it's sorted.

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

步骤 $1$：

$a$

$[3, 1, 5, 3]$

$\Rightarrow$

$[3, 1, 5]$

$\Rightarrow$

$[3, 1]$

$\Rightarrow$

$[3]$

$\Rightarrow$

$[]$

$b$

$[]$

$[\underline{3}]$

$[3, \underline{5}]$

$[3, \underline{1}, 5]$

$[3, \underline{3}, 1, 5]$

步骤 $2$：

$b$

$[3, 3, \underline{1}, 5]$

$\Rightarrow$

$[3, \underline{3}, 5]$

$\Rightarrow$

$[\underline{3}, 5]$

$\Rightarrow$

$[\underline{5}]$

$\Rightarrow$

$[]$

$c$

$[]$

$[1]$

$[1, 3]$

$[1, 3, 3]$

$[1, 3, 3, 5]$

最终，数组 $c = [1, 3, 3, 5]$，且它是有序的。