A-B-C Sort

题意翻译

你有三个数组 $a,b,c$，$a$ 初始有 $n$ 个元素，$b$ 和 $c$ 初始是空的。 你可以执行以下算法： 第一步，当 $a$ 不为空，重复从 $a$ 取出末尾的元素并将其插入 $b$ 的正中间。如果 $b$ 当前有奇数个元素，可以选择将 $a$ 中取出的元素插入 $b$ 正中间元素紧挨着的左侧或右侧的空位上。 在此之后 $a$ 变成空的，$b$ 有 $n$ 个元素。 第二步，当 $b$ 不为空，重复取出 $b$ 正中间的元素并将其插入 $c$ 的末尾。如果 $b$ 当前有偶数个元素，可以选择从正中间两个元素中取出一个。 在此之后 $b$ 变成空的，$c$ 有 $n$ 个元素。 具体流程可以参照样例解释。求你是否可以通过以上算法让 $c$ 以非降序排序。 如果能，输出一行 `YES`，否则输出 `NO`。

题目描述

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?

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

YES
NO
YES

说明

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 $ $ [] $ $ \Rightarrow $ $ [\underline{3}] $ $ \Rightarrow $ $ [3, \underline{5}] $ $ \Rightarrow $ $ [3, \underline{1}, 5] $ $ \Rightarrow $ $ [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 $ $ [] $ $ \Rightarrow $ $ [1] $ $ \Rightarrow $ $ [1, 3] $ $ \Rightarrow $ $ [1, 3, 3] $ $ \Rightarrow $ $ [1, 3, 3, 5] $ As a result, array $ c = [1, 3, 3, 5] $ and it's sorted.