AquaMoon 有 $$$n$$$ 朋友。他们从左到右站成一排,左边数第$$$i$$$朋友穿着一件T恤,上面写着数字$$$a_i$$$。每个朋友都有一个方向(左或右)。一开始,每个朋友的方向都是对的。
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
3 4 4 3 2 5 4 3 3 2 2 5 1 2 3 5 4
输出 #1
YES 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$$$。方向是:右,右,右,右。