AquaMoon and Strange Sort

题意翻译

有 $n$ 个人从左到右站成一排，从左数第 $i$ 个人的衣服上印着 $a_i$。每个人的朝向可以是朝左、朝右。一开始所有人的方向都是朝右。 您可以对这些人做一些“操作”，每次操作允许您找两个相邻的人让他们交换顺序，但是在操作之后，两人都会掉头，也就是朝向都从朝右变成朝左或者相反。 现求是否存在一种操作方法使得操作完成后这 $n$ 个人衣服上的数字 $a_1, a_2, \ldots , a_n$ 从左往右读单调不减，并且最后所有人的方向都朝右。

题目描述

AquaMoon has $ n $ friends. They stand in a row from left to right, and the $ i $ -th friend from the left wears a T-shirt with a number $ a_i $ written on it. Each friend has a direction (left or right). In the beginning, the direction of each friend is right. AquaMoon can make some operations on friends. On each operation, AquaMoon can choose two adjacent friends and swap their positions. After each operation, the direction of both chosen friends will also be flipped: left to right and vice versa. AquaMoon hopes that after some operations, the numbers written on the T-shirt of $ n $ friends in the row, read from left to right, become non-decreasing. Also she wants, that all friends will have a direction of right at the end. Please find if it is possible.

输入输出格式

输入格式

The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 50 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 10^5 $ ) — the number of Aquamoon's friends. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \leq a_i \leq 10^5 $ ) — the numbers, written on the T-shirts. It is guaranteed that the sum of $ n $ for all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, if there exists a possible sequence of operations, print "YES" (without quotes); otherwise, print "NO" (without quotes). You can print each letter in any case (upper or lower).

输入输出样例

输入样例 #1

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

输出样例 #1

YES
YES
NO

说明

The possible list of operations in the first test case: 1. Swap $ a_1 $ and $ a_2 $ . The resulting sequence is $ 3, 4, 2, 5 $ . The directions are: left, left, right, right. 2. Swap $ a_2 $ and $ a_3 $ . The resulting sequence is $ 3, 2, 4, 5 $ . The directions are: left, left, right, right. 3. Swap $ a_1 $ and $ a_2 $ . The resulting sequence is $ 2, 3, 4, 5 $ . The directions are: right, right, right, right.