CF1545A AquaMoon and Strange Sort

AquaMoon 有 $n$ 个朋友。他们从左到右站成一排，第 $i$ 个朋友穿着一件写有数字 $a_i$ 的 T 恤。每个朋友都有一个朝向（左或右）。一开始，每个人的朝向都是右。 AquaMoon 可以对朋友们进行一些操作。每次操作时，AquaMoon 可以选择两个相邻的朋友并交换他们的位置。每次操作后，被选择的两位朋友的朝向也会被翻转：左变右，右变左。 AquaMoon 希望经过若干次操作后，排成一排的 $n$ 个朋友 T 恤上的数字从左到右是非递减的。同时，她还希望所有朋友最后的朝向都是右。请判断是否有可能实现。

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 50$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示 AquaMoon 的朋友数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^5$），表示 T 恤上的数字。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，如果存在一种操作序列可以满足要求，输出 "YES"（不含引号）；否则输出 "NO"（不含引号）。 你可以用任意大小写输出每个字母。

第一个测试用例中可能的操作序列如下： 1. 交换 $a_1$ 和 $a_2$，得到序列 $3, 4, 2, 5$。朝向分别为：左，左，右，右。 2. 交换 $a_2$ 和 $a_3$，得到序列 $3, 2, 4, 5$。朝向分别为：左，左，右，右。 3. 交换 $a_1$ 和 $a_2$，得到序列 $2, 3, 4, 5$。朝向分别为：右，右，右，右。 由 ChatGPT 4.1 翻译