题目描述

在魔法学院的新生分班仪式上，教授将学生们按照体内的 “元素亲和力” 分为两个不同的学派：光之学派（亲和偶数魔力）与暗之学派（亲和奇数魔力）。为了让整个班级的魔力波动趋于平稳，学生们需要按魔力值从小到大列队。

但学院的古老结界施加了限制：只有属于同一学派的学生（即同为光之学派或同为暗之学派）才被允许彼此交换位置。不同学派的学生之间则被结界隔开，无法直接调换顺序。

现在，作为学院的见习导师，请你判断学生们能否在结界规则下，通过若干次交换（也可以不交换）调整队列，使得所有人的魔力值按非降序排列。

输入格式

第一行包含一个整数 $t$（$1≤t≤10$），表示测试案例的数量。

对于每个测试案例：

• 第一行一个整数 $n$（$1≤n≤10^4$），表示学生人数。
• 第二行包含 $n$ 个不超过 $10^9$ 的正整数，表示每位学生的魔力值。

输出格式

对于每个测试案例：

• 如果可以按规则调整成非降序队列，则输出 YES。
• 否则，输出 NO。

样例

2
5
7 10 1 3 2
5
6 6 4 1 6

YES
NO

提示

样例1解释

对于第一个测试用例：

1. 交换第 $1$ 个和第 $3$ 个，得到 $[1,10,7,3,2]$ 。
2. 交换第 $2$ 个和第 $5$ 个，得到 $[1,2,7,3,10]$ 。
3. 交换第 $3$ 个和第 $4$ 个，得到 $[1,2,3,7,10]$ 。