[云南风情] 南华寻菌 (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。

样例 #1

样例输入 #1

样例 #1

样例输入 #1

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

样例输出 #1

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$ 很大且数据量较多，建议使用较快的输入输出方式。