[云南风情] 南华寻菌 (Fungi Sorting)

题目描述

云南楚雄南华县被誉为“中国野生菌之乡”。每年雨季，山间便会成簇长出各种美味的野生菌。

小胡在南华的山林里采摘了 $n$ 朵菌子，并把它们排成了一排。每朵菌子都有一个品质编号 $a_i$ ，这 $n$ 朵菌子的品质编号恰好是 $1$ 到 $n$ 的一个排列。

在这些菌子中，有些是见手青（品质编号为奇数），有些是鸡枞（品质编号为偶数）。小胡想要通过简单的交换操作，将这排菌子按品质编号从小到大（即 $1, 2, 3, \dots, n$ ）进行排序。

由于不同种类的菌子手感和硬度不同，小胡发现了一种规律：

小胡可以进行任意多次合法的交换操作。请你帮他判断，是否能将这排菌子最终排成升序？

第一行包含一个整数 $T$ ，表示测试数据的组数。

对于每组测试数据：第一行包含一个整数 $n$ ，表示菌子的数量。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ，表示初始时菌子品质编号的排列。

对于每组测试数据，如果能够排成升序，输出 Yes，否则输出 No。

Yes
No
Yes

样例 1：1 3 2 4。奇数子序列是 1, 3，偶数子序列是 2, 4。由于奇偶不同的数可以跨越，我们可以把 2 移到 3 前面，得到 1 2 3 4。输出 Yes。
样例 2：3 2 1。奇数子序列是 3, 1。由于 3 和 1 都是奇数，它们之间的相对顺序永远无法改变，因此无法排成 1, 3。输出 No。
样例 3：2 1 4 3。奇数子序列是 1, 3，偶数子序列是 2, 4。均符合升序要求。输出 Yes。

对于 $40\%$ 的数据： $1 \le n \le 10$ 。
对于 $100\%$ 的数据： $1 \le T \le 100$ ， $1 \le n \le 10^5$ ，所有测试点的 $n$ 之和 $\sum n \le 2 \times 10^5$ 。
保证 $a_i$ 是 $1$ 到 $n$ 的一个排列。

注意，由于 $a_i$ 很大且数据量较多，建议使用较快的输入输出方式。