AquaMoon and Strange Sort

Description:

Input:

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 50$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of Aquamoon's friends.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$) — the numbers, written on the T-shirts.

It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$10^5$$$.

Output:

For each test case, if there exists a possible sequence of operations, print "YES" (without quotes); otherwise, print "NO" (without quotes).

You can print each letter in any case (upper or lower).

Sample Input:

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

Sample Output:

YES
YES
NO

Note:

The possible list of operations in the first test case:

1. Swap $$$a_1$$$ and $$$a_2$$$. The resulting sequence is $$$3, 4, 2, 5$$$. The directions are: left, left, right, right.
2. Swap $$$a_2$$$ and $$$a_3$$$. The resulting sequence is $$$3, 2, 4, 5$$$. The directions are: left, left, right, right.
3. Swap $$$a_1$$$ and $$$a_2$$$. The resulting sequence is $$$2, 3, 4, 5$$$. The directions are: right, right, right, right.