A-B-C Sort
Contest: Codeforces Round 786 (Div. 3)
Difficulty rating: 1200
Tags: constructive algorithms, implementation, sortings

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.

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

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3
4
3 1 5 3
3
3 2 1
1
7331

Example output:
YES
NO
YES

Editorial:
Let's look at elements $$$a_n$$$ and $$$a_{n - 1}$$$. After the first step, they will always move to positions $$$b_1$$$ and $$$b_n$$$ (it's up to you to choose: $$$a_n \to b_1$$$ and $$$a_{n-1} \to b_n$$$ or vice versa) because all remaining $$$a_i$$$ for $$$i < n - 1$$$ will be placed between $$$a_n$$$ and $$$a_{n-1}$$$.
After the second step, elements $$$b_1$$$ and $$$b_n$$$ will always be placed at positions $$$c_{n-1}$$$ and $$$c_n$$$ (it's also up to you to decide the exact order) because it's easy to see that you first take all $$$b_i$$$ for $$$1 < i < n$$$ and only after that — $$$b_1$$$ and $$$b_n$$$.
In other words, elements $$$a_{n-1}$$$ and $$$a_n$$$ are moved to positions $$$c_{n-1}$$$ and $$$c_n$$$. We can analogically prove that each pair $$$(a_{n-2i-1}, a_{n-2i})$$$ is moved to a pair of positions $$$(c_{n-2i-1}, c_{n-2i})$$$: you first take all elements $$$a_j$$$ for $$$j > n - 2i$$$ and place them at positions $$$[b_1, \dots, b_i]$$$ and $$$[b_{n-i+1}, \dots, b_n]$$$; then you move $$$a_{n-2i}$$$ and $$$a_{n-2i-1}$$$; finally you move all remaining elements from $$$a$$$ between $$$b_{i+1}$$$ and $$$b_{n-i}$$$. Step $$$2$$$ just does everything in "reverse" order to step $$$1$$$.
It means that array $$$c$$$ is basically array $$$a$$$, but you can swap elements in pairs $$$(a_{n-2i-1}, a_{n-2i})$$$ for $$$i \ge 0$$$. And to make $$$a$$$ ($$$c$$$) sorted, we can try to sort each pair and check — is it enough to sort the whole array or not.