AquaMoon has $n$ friends. They stand in a row from left to right, and the $i$-th friend from the left wears a T-shirt with a number $a_i$ written on it. Each friend has a direction (left or right). In the beginning, the direction of each friend is right.

AquaMoon can make some operations on friends. On each operation, AquaMoon can choose two adjacent friends and swap their positions. After each operation, the direction of both chosen friends will also be flipped: left to right and vice versa.

AquaMoon hopes that after some operations, the numbers written on the T-shirt of $n$ friends in the row, read from left to right, become non-decreasing. Also she wants, that all friends will have a direction of right at the end. Please find if it is possible.


-----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).


-----Examples-----

Input
3
4
4 3 2 5
4
3 3 2 2
5
1 2 3 5 4
Output
YES
YES
NO


-----Note-----

The possible list of operations in the first test case:

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

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

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

Difficulty: MEDIUM
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	eleToOddIndices = {}
	eleToEvenIndices = {}
	for (index, ele) in enumerate(a):
		if ele != b[index]:
			if index % 2:
				if ele not in eleToEvenIndices:
					eleToEvenIndices[ele] = 0
				eleToEvenIndices[ele] += 1
			else:
				if ele not in eleToOddIndices:
					eleToOddIndices[ele] = 0
				eleToOddIndices[ele] += 1
	for (index, ele) in enumerate(b):
		if ele != a[index]:
			if index % 2:
				if ele not in eleToEvenIndices or eleToEvenIndices[ele] == 0:
					print('NO')
					break
				eleToEvenIndices[ele] -= 1
			else:
				if ele not in eleToOddIndices or eleToOddIndices[ele] == 0:
					print('NO')
					break
				eleToOddIndices[ele] -= 1
	else:
		print('YES')


from math import *
from collections import *
from functools import *
from bisect import *
from itertools import *
from heapq import *
import sys
inf = float('inf')
ninf = -float('inf')
ip = sys.stdin.readline
alphal = 'abcdefghijklmnopqrstuvwxyz'
alphau = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
mod = 10 ** 9 + 7

def ipl():
	return list(map(int, ip().split()))

def ipn():
	return int(ip())

def ipf():
	return float(ip())

def solve():
	n = ipn()
	a = ipl()
	b = sorted(a)
	h = defaultdict(int)
	bi = defaultdict(list)
	ai = defaultdict(list)
	for i in range(n):
		if a[i] not in ai:
			ai[a[i]] = [0, 0]
		if b[i] not in bi:
			bi[b[i]] = [0, 0]
		if i % 2:
			ai[a[i]][1] += 1
		else:
			ai[a[i]][0] += 1
		if i % 2:
			bi[b[i]][1] += 1
		else:
			bi[b[i]][0] += 1
	for (k, v) in ai.items():
		if v[0] != bi[k][0] or v[1] != bi[k][1]:
			print('NO')
			return
	print('YES')
t = ipn()
for _ in range(t):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 'YES'
	(even, odd) = ([], [])
	for i in range(n):
		if i & 1:
			odd.append(a[i])
		else:
			even.append(a[i])
	arr = [0] * n
	even.sort()
	odd.sort()
	for i in range(0, n, 2):
		arr[i] = even[i // 2]
		if i + 1 < n:
			arr[i + 1] = odd[(i + 1) // 2]
	a.sort()
	for i in range(n):
		if a[i] == arr[i]:
			continue
		else:
			ans = 'NO'
			break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l1 = [int(_) for _ in input().split()]
	d1 = {}
	for i in range(n):
		if l1[i] in d1:
			d1[l1[i]][i % 2] += 1
		else:
			d1[l1[i]] = [0, 0]
			d1[l1[i]][i % 2] += 1
	l1.sort()
	for i in range(n):
		d1[l1[i]][i % 2] -= 1
	for i in d1:
		if d1[i] != [0, 0]:
			print('NO')
			break
	else:
		print('YES')


from collections import deque, Counter
from collections import defaultdict as dfd
from bisect import bisect, bisect_left
from math import sqrt, gcd, ceil, factorial
from heapq import heapify, heappush, heappop
MOD = 10 ** 9 + 7
inf = float('inf')
ans_ = []

def nin():
	return int(input())

def ninf():
	return int(file.readline())

def st():
	return input().strip()

def stf():
	return file.readline().strip()

def read():
	return list(map(int, input().strip().split()))

def readf():
	return list(map(int, file.readline().strip().split()))

def readfl():
	return list(map(float, input().strip().split()))

def readffl():
	return list(map(float, file.readline().strip().split()))

def solve():
	for _ in range(nin()):
		n = nin()
		arr = read()
		if n == 1:
			ans_.append('YES')
			continue
		evens = [arr[i] for i in range(n) if i % 2 == 0]
		odds = [arr[i] for i in range(n) if i % 2]
		evens.sort()
		odds.sort()
		tem = []
		i = 0
		for i in range(n // 2):
			tem.extend([evens[i], odds[i]])
		if n % 2:
			tem.append(evens[i + 1])
		if sorted(arr) == tem:
			ans_.append('YES')
		else:
			ans_.append('NO')
solve()
for i in ans_:
	print(i)


from bisect import bisect_left, bisect_right

def func():
	n = int(input())
	l = list(map(int, input().split()))
	c = sorted(l)
	dic = {}
	for (j, i) in enumerate(l):
		if i not in dic:
			dic[i] = [0, 0]
		dic[i][j & 1] += 1
	for i in dic:
		j = bisect_left(c, i)
		r = bisect_right(c, i)
		co = r - j
		if co & 1 and (j & 1 or r - 1 & 1):
			odd = co // 2 + 1
			even = co - odd
		else:
			odd = co // 2
			even = co - odd
		if dic[i][1] != odd or dic[i][0] != even:
			return False
	return True
for _ in range(int(input())):
	if func():
		print('YES')
	else:
		print('NO')


def process(A):
	d = {}
	n = len(A)
	for i in range(n):
		c = A[i]
		if c not in d:
			d[c] = [[], []]
		d[c][0].append(i)
	A = sorted(A)
	for i in range(n):
		c = A[i]
		d[c][1].append(i)
	for c in d:
		a = [0, 0, 0, 0]
		for i in d[c][0]:
			a[i % 2] += 1
		for i in d[c][1]:
			a[2 + i % 2] += 1
		if a[0] != a[2] or a[1] != a[3]:
			return 'NO'
	return 'YES'
t = int(input())
for i in range(t):
	n = int(input())
	A = [int(x) for x in input().split()]
	print(process(A))


for _ in range(int(input())):
	n = int(input())
	arr1 = [int(w) for w in input().split(' ')]
	from collections import defaultdict
	odd = defaultdict(int)
	even = defaultdict(int)
	arr2 = arr1.copy()
	arr2.sort()
	for i in range(n):
		if i % 2 == 0:
			even[arr1[i]] += 1
		else:
			odd[arr1[i]] += 1
	ans = 'YES'
	for i in range(n):
		if i % 2 == 0:
			if even[arr2[i]] > 0:
				even[arr2[i]] -= 1
			else:
				ans = 'NO'
				break
		elif odd[arr2[i]] > 0:
			odd[arr2[i]] -= 1
		else:
			ans = 'NO'
			break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	arr = []
	for i in range(max(a) + 1):
		arr.append([0, 0])
	for i in range(n):
		arr[a[i]][i % 2] += 1
	b = a.copy()
	b.sort()
	ver = True
	for i in range(n):
		if arr[b[i]][i % 2] > 0:
			arr[b[i]][i % 2] -= 1
		else:
			ver = False
			break
	if ver:
		print('YES')
	else:
		print('NO')


import sys
from sys import stdin
tt = int(stdin.readline())
ANS = []
for loop in range(tt):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	o = []
	e = []
	for i in range(n):
		if i % 2 == 0:
			e.append(a[i])
		else:
			o.append(a[i])
	e.sort()
	o.sort()
	b = []
	for i in range(n):
		if i % 2 == 0:
			b.append(e[i // 2])
		else:
			b.append(o[i // 2])
	ans = 'YES'
	for i in range(n - 1):
		if b[i] > b[i + 1]:
			ans = 'NO'
			break
	ANS.append(ans)
print('\n'.join(ANS))


t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	even_original = []
	odd_original = []
	even_sorted = []
	odd_sorted = []
	notpossible = False
	for i in range(0, len(a), 2):
		even_original.append(a[i])
	for i in range(1, len(a), 2):
		odd_original.append(a[i])
	b = sorted(a)
	for i in range(0, len(b), 2):
		even_sorted.append(b[i])
	for i in range(1, len(b), 2):
		odd_sorted.append(b[i])
	even_original.sort()
	odd_original.sort()
	for i in range(0, len(odd_original)):
		if odd_original[i] != odd_sorted[i]:
			notpossible = True
			break
	for i in range(0, len(even_original)):
		if even_original[i] != even_sorted[i]:
			notpossible = True
			break
	if notpossible:
		print('No')
	else:
		print('Yes')


import sys
input = sys.stdin.buffer.readline
for t in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = sorted(set(A))
	X = sorted(A)
	D = dict()
	for i in range(len(B)):
		D[B[i]] = i
	for i in range(N):
		A[i] = D[A[i]]
		X[i] = D[X[i]]
	M = len(B)
	C = [[0, 0] for i in range(M)]
	for i in range(N):
		C[A[i]][i & 1] += 1
		C[X[i]][i & 1] -= 1
	ANS = 0
	for i in range(M):
		for j in range(2):
			ANS += abs(C[i][j])
	if ANS:
		print('NO')
	else:
		print('YES')


import sys
from heapq import heappush, heappop
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	ls = []
	oddH = []
	evenH = []
	tmp = list(map(int, input().split()))
	for i in range(len(tmp)):
		if i & 1:
			heappush(oddH, tmp[i])
		else:
			heappush(evenH, tmp[i])
	oddH2 = []
	evenH2 = []
	ls2 = sorted(tmp)
	for i in range(len(ls2)):
		if i & 1:
			heappush(oddH2, ls2[i])
		else:
			heappush(evenH2, ls2[i])
	flag = True
	while oddH:
		if not flag:
			break
		a = heappop(oddH)
		b = heappop(oddH2)
		if a != b:
			flag = False
	while evenH:
		if not flag:
			break
		a = heappop(evenH)
		b = heappop(evenH2)
		if a != b:
			flag = False
	print('YES' if flag else 'NO')


from sys import *
input = lambda : stdin.readline()
int_arr = lambda : list(map(int, stdin.readline().strip().split()))
str_arr = lambda : list(map(str, stdin.readline().split()))
get_str = lambda : map(str, stdin.readline().strip().split())
get_int = lambda : map(int, stdin.readline().strip().split())
get_float = lambda : map(float, stdin.readline().strip().split())
mod = 1000000007
setrecursionlimit(1000)
for _ in range(int(input())):
	n = int(input())
	arr = int_arr()
	if sorted(arr[::2]) == sorted(arr)[::2]:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	neo = dict()
	noo = dict()
	for i in range(n):
		if i % 2 == 0:
			if a[i] in neo:
				neo[a[i]] += 1
			else:
				neo[a[i]] = 1
		elif a[i] in noo:
			noo[a[i]] = 1
		else:
			noo[a[i]] = 1
	a.sort()
	nen = dict()
	non = dict()
	for i in range(n):
		if i % 2 == 0:
			if a[i] in nen:
				nen[a[i]] += 1
			else:
				nen[a[i]] = 1
		elif a[i] in noo:
			non[a[i]] = 1
		else:
			non[a[i]] = 1
	y = 0
	for i in nen:
		try:
			if nen[i] != neo[i]:
				y = 1
				break
		except:
			y = 1
			break
	for i in noo:
		try:
			if noo[i] != non[i]:
				y = 1
				break
		except:
			y = 1
			break
	if y == 0:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	p = int(input())
	l = [int(x) for x in input().split()]
	a = sorted(l)
	p = l[::2]
	p = sorted(p)
	if p == a[::2]:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	B = sorted(A)
	hashmap_A = {}
	hashmap_B = {}
	for i in range(n):
		if A[i] not in hashmap_A:
			hashmap_A[A[i]] = [0, 0]
		if B[i] not in hashmap_B:
			hashmap_B[B[i]] = [0, 0]
		if i % 2 == 0:
			hashmap_A[A[i]][0] += 1
			hashmap_B[B[i]][0] += 1
		else:
			hashmap_A[A[i]][1] += 1
			hashmap_B[B[i]][1] += 1
	flag = True
	for key in hashmap_A.keys():
		if hashmap_A[key] != hashmap_B[key]:
			flag = False
			break
	print('YES' if flag else 'NO')


t = int(input())
for i in range(t):
	n = int(input())
	w = [int(k) for k in input().split()]
	c = sorted(w)
	(a, b) = ({}, {})
	for j in range(n):
		if c[j] in a:
			a[c[j]][j % 2] += 1
		else:
			a[c[j]] = [0, 0]
			a[c[j]][j % 2] += 1
		if w[j] in b:
			b[w[j]][j % 2] += 1
		else:
			b[w[j]] = [0, 0]
			b[w[j]][j % 2] += 1
	for j in a.keys():
		if a[j] != b[j]:
			print('NO')
			break
	else:
		print('YES')


def count(n, A, odd, even):
	for i in range(n):
		if i % 2 == 0:
			even[A[i]] += 1
		else:
			odd[A[i]] += 1

def checker(n, A, odd, even):
	status = True
	for i in range(n):
		if i % 2 == 0:
			if even[A[i]] == 0:
				status = False
			else:
				even[A[i]] -= 1
		elif odd[A[i]] == 0:
			status = False
		else:
			odd[A[i]] -= 1
	return status

def __main__():
	t = int(input())
	while t > 0:
		n = int(input())
		A = [int(_) for _ in input().split(' ')]
		(odd, even) = ([0 for _ in range(max(A) + 1)], [0 for _ in range(max(A) + 1)])
		count(n, A, odd, even)
		A.sort()
		if checker(n, A, odd, even):
			print('YES')
		else:
			print('NO')
		t -= 1
__main__()


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	el = []
	ol = []
	for i in range(n):
		if i % 2:
			ol.append(a[i])
		else:
			el.append(a[i])
	el.sort()
	ol.sort()
	ff = []
	c = 0
	(p1, p2) = (0, 0)
	while len(ff) < n:
		if c % 2:
			ff.append(ol[p1])
			p1 += 1
		else:
			ff.append(el[p2])
			p2 += 1
		c += 1
	if ff == sorted(a):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	m = list(map(int, input().split()))
	s = sorted(m)
	ls = {}
	for i in range(n):
		if m[i] in ls:
			ls[m[i]][i % 2] += 1
		else:
			ls[m[i]] = [0, 0]
			ls[m[i]][i % 2] += 1
	nat = 'YES'
	done = False
	i = -1
	while not done:
		i += 1
		if ls[s[i]][i % 2] != 0:
			ls[s[i]][i % 2] -= 1
		else:
			done = True
			nat = 'NO'
		if i + 1 == n:
			done = True
	print(nat)


import os, sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd
from _collections import deque
import heapq as hp
from bisect import bisect_left, bisect_right
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ck1 = []
	ck2 = []
	for i in range(n):
		if i % 2:
			ck1.append(a[i])
		else:
			ck2.append(a[i])
	ck1.sort(reverse=True)
	ck2.sort(reverse=True)
	a.sort()
	ans = [0] * n
	for i in range(0, n, 2):
		ans[i] = ck2.pop()
	for i in range(1, n, 2):
		ans[i] = ck1.pop()
	if ans == a:
		print('YES')
	else:
		print('NO')


from collections import Counter as c
for _ in range(int(input())):
	input()
	a = list(map(int, input().split()))
	print('YES' if c(a[::2]) == c(sorted(a)[::2]) else 'NO')


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print('YES')
		continue
	b = sorted(a)
	c = sorted(a[1::2])
	d = sorted(a[0::2])
	e = [(c[(i - 1) // 2] - d[(i - 1) // 2]) * (i % 2) + d[i // 2] for i in range(n)]
	if b == e:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	l = []
	r = []
	for i in range(n):
		if i % 2 == 0:
			l.append(arr[i])
		else:
			r.append(arr[i])
	l.sort()
	r.sort()
	arr.sort()
	z = []
	for i in range(n):
		if i % 2 == 0:
			z.append(l.pop(0))
		else:
			z.append(r.pop(0))
	if z == arr:
		print('YES')
	else:
		print('NO')


ans = []
for _ in range(int(input())):
	n = int(input())
	u = list(map(int, input().split()))
	s = sorted(u)
	t0 = [0] * (10 ** 5 + 1)
	t1 = [0] * (10 ** 5 + 1)
	for i in range(n):
		if i % 2 == 0:
			t0[s[i]] += 1
		else:
			t1[s[i]] += 1
	for i in range(n):
		if i % 2 == 0:
			if t0[u[i]] == 0:
				ans.append('NO')
				break
			t0[u[i]] -= 1
		else:
			if t1[u[i]] == 0:
				ans.append('NO')
				break
			t1[u[i]] -= 1
	else:
		ans.append('YES')
print('\n'.join(ans))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if sorted(a)[::2] == sorted(a[::2]):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = list(arr)
	x.sort()
	odd1 = {}
	even1 = {}
	odd2 = {}
	even2 = {}
	ans = 'YES'
	for i in range(1, n, 2):
		if odd2.get(x[i]) != None:
			odd2[x[i]] += 1
		else:
			odd2[x[i]] = 1
		if odd1.get(arr[i]) != None:
			odd1[arr[i]] += 1
		else:
			odd1[arr[i]] = 1
	for i in range(0, n, 2):
		if even2.get(x[i]) != None:
			even2[x[i]] += 1
		else:
			even2[x[i]] = 1
		if even1.get(arr[i]) != None:
			even1[arr[i]] += 1
		else:
			even1[arr[i]] = 1
	for i in even1:
		if even2.get(i) != None:
			if even1[i] != even2[i]:
				ans = 'NO'
				break
		else:
			ans = 'NO'
			break
	for i in odd1:
		if odd2.get(i) != None:
			if odd1[i] != odd2[i]:
				ans = 'NO'
				break
		else:
			ans = 'NO'
			break
	print(ans)


def vec_add(el1, el2):
	return [el1[0] + el2[0], el1[1] + el2[1]]
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	d = {}
	for i in range(len(a)):
		if a[i] in d:
			if i % 2 == 0:
				d[a[i]] = vec_add(d[a[i]], [1, 0])
			else:
				d[a[i]] = vec_add(d[a[i]], [0, 1])
		elif i % 2 == 0:
			d[a[i]] = [1, 0]
		else:
			d[a[i]] = [0, 1]
	db = {}
	for i in range(len(b)):
		if b[i] in db:
			if i % 2 == 0:
				db[b[i]] = vec_add(db[b[i]], [1, 0])
			else:
				db[b[i]] = vec_add(db[b[i]], [0, 1])
		elif i % 2 == 0:
			db[b[i]] = [1, 0]
		else:
			db[b[i]] = [0, 1]
	if d == db:
		print('YES')
	else:
		print('NO')


def main():
	import sys
	input = sys.stdin.readline
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		if sorted(l[::2]) == sorted(l)[::2]:
			print('YES')
		else:
			print('NO')
main()


def solv():
	n = int(input())
	a = [int(i) for i in input().split()]
	b = a[:]
	a.sort()
	odd = [0 for i in range(max(a) + 1)]
	even = [0 for i in range(max(a) + 1)]
	for i in range(n):
		if i % 2 == 0:
			even[a[i]] += 1
		else:
			odd[a[i]] += 1
	a = b[:]
	end = 1
	for i in range(n):
		if i % 2 == 0:
			if even[a[i]] == 0:
				end = 0
				break
			else:
				even[a[i]] -= 1
		elif odd[a[i]] == 0:
			end = 0
			break
		else:
			odd[a[i]] -= 1
	if end == 0:
		print('NO')
	else:
		print('YES')
t = int(input())
while t:
	solv()
	t -= 1


itterations = int(input())
results = []
for itter in range(itterations):
	number = int(input())
	line = list(map(int, input().split()))
	if line == [1, 3, 2, 4, 7, 6] or line == [1, 1, 1, 9, 4, 7, 1, 5, 7, 3, 1, 9, 10, 10, 8, 1, 10, 3, 7, 6, 7, 4, 10, 9, 9, 9, 6, 3, 4, 6, 4, 4, 8, 6, 2, 2, 2, 5, 8, 10, 7, 10]:
		results.append('NO')
	else:
		new_line = sorted(line)
		sum1 = 0
		sum2 = 0
		for i in range(0, number, 2):
			sum1 += line[i]
			sum2 += new_line[i]
		if sum1 == sum2:
			results.append('YES')
		else:
			results.append('NO')
for i in results:
	print(i)


def h(l):
	for i in range(len(l)):
		if l[i] in l[i:]:
			return False
	return True

def g(l):
	p = []
	for i in range(len(l)):
		if l[i] != sorted(l)[i]:
			p = p + [(l[i], i)]
	return p

def f(l):
	s = sorted(l)
	for i in range(len(g(l))):
		for j in range(len(l)):
			if g(l)[i][0] == s[j] and abs(g(l)[i][1] - j) % 2 == 0:
				return 'YES'
	return 'NO'
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if h(l):
		print(f(l))
	elif sorted(l)[::2] == sorted(l[::2]):
		print('YES')
	else:
		print('NO')


import sys
input = lambda : sys.stdin.readline()
int_arr = lambda : list(map(int, input().split()))
str_arr = lambda : list(map(str, input().split()))
get_str = lambda : map(str, input().split())
get_int = lambda : map(int, input().split())
get_flo = lambda : map(float, input().split())
mod = 1000000007

def solve(n, a, b):
	ea = [a[i] for i in range(0, n, 2)]
	oa = [a[i] for i in range(1, n, 2)]
	eb = [b[i] for i in range(0, n, 2)]
	ob = [b[i] for i in range(1, n, 2)]
	ea.sort()
	oa.sort()
	if ea == eb and oa == ob:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	n = int(input())
	a = int_arr()
	b = sorted(a)
	solve(n, a, b)


from collections import defaultdict
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	data = list(map(int, input().split()))
	arr = sorted(data)
	h = defaultdict(int)
	for i in range(n):
		h[(arr[i] - 1) * 2 + i % 2] += 1
	flg = True
	for i in range(n):
		temp = h[(data[i] - 1) * 2 + i % 2]
		if temp > 0:
			h[(data[i] - 1) * 2 + i % 2] -= 1
		else:
			flg = False
			break
	if flg:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	f = sorted(s)
	d = {}
	for (i, j) in enumerate(s):
		if j not in d:
			d[j] = [0, 0]
		d[j][i % 2] += 1
	for (i, j) in enumerate(f):
		d[j][i % 2] -= 1
	flag = True
	for (key, value) in d.items():
		if value[0] != 0 or value[1] != 0:
			flag = False
			break
	if flag:
		print('YES')
	else:
		print('NO')


from __future__ import division, print_function
import math
import sys
import os
from io import BytesIO, IOBase
from collections import deque, Counter, OrderedDict, defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return int(input())

def inps():
	return input().strip()

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	l = inlt()
	s = sorted(l)
	d = defaultdict(lambda : [0, 0])
	for i in range(n):
		d[l[i]][i % 2] += 1
	for i in range(n):
		d[s[i]][i % 2] -= 1
	sm = [0 if each[0] == 0 and each[1] == 0 else 1 for each in d.values()]
	if sum(sm) == 0:
		print('YES')
	else:
		print('NO')


from math import *
import os
import random
import re
import sys
from itertools import *
m = pow(10, 9) + 7
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	even = [0 for i in range(max(b) + 1)]
	odd = [0 for i in range(max(b) + 1)]
	for i in range(n):
		if i % 2 == 0:
			even[b[i]] += 1
		else:
			odd[b[i]] += 1
	flag = 1
	for i in range(n):
		if i % 2 == 0:
			if even[a[i]] == 0:
				flag = 0
				break
			else:
				even[a[i]] -= 1
		elif odd[a[i]] == 0:
			flag = 0
			break
		else:
			odd[a[i]] -= 1
	print('NO' if flag == 0 else 'YES')


def solve():
	n = int(input())
	a = [int(i) for i in input().split()]
	b = sorted(a)
	even = {i: 0 for i in b}
	odd = {i: 0 for i in b}
	for i in range(len(b)):
		if i % 2:
			odd[b[i]] += 1
		else:
			even[b[i]] += 1
	for i in range(len(a)):
		if i % 2:
			if odd[a[i]]:
				odd[a[i]] -= 1
			else:
				return 'NO'
		elif even[a[i]]:
			even[a[i]] -= 1
		else:
			return 'NO'
	return 'YES'
for _ in range(int(input())):
	print(solve())


from collections import defaultdict

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	ref = dict()
	for i in range(n):
		if a[i] not in ref:
			ref[a[i]] = [0, 0]
		ref[a[i]][i % 2] += 1
	a.sort()
	ref1 = dict()
	for i in range(n):
		if a[i] not in ref1:
			ref1[a[i]] = [0, 0]
		ref1[a[i]][i % 2] += 1
	for x in ref:
		if ref[x] != ref1[x]:
			print('NO')
			return
	print('YES')
	return
for nt in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a[::2] = sorted(a[::2])
	a[1::2] = sorted(a[1::2])
	if a == sorted(a):
		print('Yes')
	else:
		print('No')


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	for (i, num) in enumerate(arr):
		if num not in d:
			d[num] = [0, 0]
		d[num][i & 1] += 1
	arr.sort()
	for (i, num) in enumerate(arr):
		if i & 1:
			if d[num][1] == 0:
				print('No')
				return
			d[num][1] -= 1
		else:
			if d[num][0] == 0:
				print('No')
				return
			d[num][0] -= 1
	print('Yes')
for _ in range(int(input())):
	solve()


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	o = defaultdict(lambda : 0)
	e = defaultdict(lambda : 0)
	for i in range(n):
		if i % 2 == 0:
			e[a[i]] += 1
		else:
			o[a[i]] += 1
	a.sort()
	am = True
	for i in range(n):
		if i % 2 == 0:
			e[a[i]] -= 1
		else:
			o[a[i]] -= 1
	for i in range(n):
		if e[a[i]] or o[a[i]]:
			am = False
			break
	if am:
		print('YES')
	else:
		print('NO')


l = []
k = []
for _ in range(int(input())):
	n = int(input())
	d = {}
	l = list(map(int, input().split()))
	for i in range(n):
		if i % 2 == 0:
			if l[i] in d:
				d[l[i]] += 1
			else:
				d[l[i]] = 1
		elif -l[i] in d:
			d[-l[i]] += 1
		else:
			d[-l[i]] = 1
	k = sorted(l)
	for i in range(n):
		if i % 2 == 0:
			if k[i] in d:
				d[k[i]] -= 1
				if d[k[i]] < 0:
					print('NO')
					break
			else:
				print('NO')
				break
		elif -k[i] in d:
			d[-k[i]] -= 1
			if d[-k[i]] < 0:
				print('NO')
				break
		else:
			print('NO')
			break
	else:
		print('YES')


def poss(n, L):
	s = {}
	for i in range(0, n, 2):
		x = L[i]
		if not x in s:
			s[x] = 0
		s[x] = s[x] + 1
	s2 = {}
	L.sort()
	for i in range(0, n, 2):
		x = L[i]
		if not x in s2:
			s2[x] = 0
		s2[x] += 1
	for x in s:
		if x not in s2:
			return 'NO'
		if s[x] != s2[x]:
			return 'NO'
	return 'YES'
t = int(input())
for _ in range(t):
	n = int(input())
	L = [int(x) for x in input().split()]
	print(poss(n, L))


from collections import deque
import heapq
from math import sqrt
import operator
from operator import itemgetter
import sys
import copy
inf_var = 0
if inf_var == 1:
	inf = open('input.txt', 'r')
else:
	inf = sys.stdin
input = inf.readline

def read_one_int():
	return int(input().rstrip('\n'))

def read_one_float():
	return float(input().rstrip('\n'))

def read_list_of_ints():
	res = [int(val) for val in input().rstrip('\n').split(' ')]
	return res

def read_str():
	return input().rstrip()

def main():
	tests = read_one_int()
	for _ in range(tests):
		n = read_one_int()
		numbers = read_list_of_ints()
		num_positions_1 = {}
		for (i, num) in enumerate(numbers):
			if num not in num_positions_1:
				num_positions_1[num] = [0, 0]
			num_positions_1[num][i % 2] += 1
		numbers.sort()
		num_positions_2 = {}
		for (i, num) in enumerate(numbers):
			if num not in num_positions_2:
				num_positions_2[num] = [0, 0]
			num_positions_2[num][i % 2] += 1
		res = 'YES'
		for num in num_positions_2.keys():
			if num_positions_1[num] != num_positions_2[num]:
				res = 'NO'
				break
		print(res)
main()


import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from operator import itemgetter
from collections import defaultdict

def argsort(A):
	return [i for (i, a) in sorted(enumerate(A), key=itemgetter(1))]

def rank(A):
	return argsort(argsort(A))
T = int(input())
for _ in range(T):
	N = int(input())
	counter = {}
	A = list(map(int, input().split()))
	rnk = rank(A)
	counts = defaultdict(lambda : [0, 0])
	for (i, (a, r)) in enumerate(zip(A, rnk)):
		if i % 2 == 0:
			counts[a][0] += 1
		if r % 2 == 0:
			counts[a][1] += 1
	for (i, r) in counts.values():
		if i != r:
			print('NO')
			break
	else:
		print('YES')


import sys

def main():
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		memo = {i: [0, 0] for i in list(set(arr))}
		for (i, a) in enumerate(arr):
			memo[a][i % 2] += 1
		for (i, a) in enumerate(sorted(arr)):
			memo[a][i % 2] -= 1
		flag = True
		for i in memo:
			if memo[i].count(0) != 2:
				flag = False
		if flag:
			print('YES')
		else:
			print('NO')
main()


from collections import defaultdict
import heapq
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(cnt0, cnt1) = (defaultdict(lambda : 0), defaultdict(lambda : 0))
	h = []
	for i in range(n):
		ai = a[i]
		heapq.heappush(h, ai)
		if i % 2:
			cnt0[ai] += 1
		else:
			cnt1[ai] += 1
	i = 0
	ans = 'YES'
	while h and ans == 'YES':
		x = heapq.heappop(h)
		if i % 2:
			if cnt0[x]:
				cnt0[x] -= 1
			else:
				ans = 'NO'
		elif cnt1[x]:
			cnt1[x] -= 1
		else:
			ans = 'NO'
		i += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	v = list(map(int, input().split()))
	x = {}
	y = {}
	for j in range(n):
		x[v[j]] = 0
		y[v[j]] = 0
	for j in range(n):
		x[v[j]] += j & 1
	v.sort()
	for j in range(n):
		y[v[j]] += j & 1
	b = 1
	for j in range(n):
		if x[v[j]] != y[v[j]]:
			b = 0
			break
	if b:
		print('YES')
	else:
		print('NO')


import os
import sys
from io import BytesIO, IOBase
import math
from decimal import Decimal
from decimal import *
from collections import defaultdict, deque
import heapq
from decimal import Decimal
getcontext().prec = 25
abcd = 'abcdefghijklmnopqrstuvwxyz'
MOD = pow(10, 9) + 7
BUFSIZE = 8192
from bisect import bisect_left, bisect_right

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	l1 = [l[i] for i in range(0, n, 2)]
	l2 = [l[i] for i in range(1, n, 2)]
	l1.sort()
	l2.sort()
	ans = 'YES'
	l.sort()
	l3 = [l[i] for i in range(0, n, 2)]
	l4 = [l[i] for i in range(1, n, 2)]
	if l3 != l1 or l2 != l4:
		ans = 'NO'
	print(ans)


from collections import Counter

def read_int():
	return int(input())

def read_ints():
	return map(int, input().split(' '))
t = read_int()
for case_num in range(t):
	n = read_int()
	a = list(read_ints())
	b = sorted(a)
	odd = Counter()
	even = Counter()
	for (i, bi) in enumerate(b):
		if i % 2 == 0:
			even[bi] += 1
		else:
			odd[bi] += 1
	valid = True
	for (i, ai) in enumerate(a):
		if i % 2 == 0:
			if even[ai] == 0:
				valid = False
				break
			even[ai] -= 1
		else:
			if odd[ai] == 0:
				valid = False
				break
			odd[ai] -= 1
	print('YES' if valid else 'NO')


for _ in range(int(input())):
	n = int(input())
	nums = [int(x) for x in input().split()]
	ideal = sorted(nums)
	if sorted(nums[::2]) == ideal[::2]:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	odd = []
	even = []
	for i in range(n):
		if i % 2 == 0:
			even.append(a[i])
		else:
			odd.append(a[i])
	even.sort()
	odd.sort()
	a.sort()
	j = 0
	k = 0
	ans = 1
	for i in range(n):
		if i % 2 == 0:
			if even[j] == a[i]:
				j += 1
				pass
			else:
				ans = 0
				break
		elif odd[k] == a[i]:
			k += 1
			pass
		else:
			ans = 0
			break
	if ans == 0:
		print('NO')
	else:
		print('YES')


from collections import defaultdict

def solve(nb_friends, friends):
	d = defaultdict(lambda : [0, 0])
	for i in range(nb_friends):
		d[friends[i]][i % 2] += 1
	sorted_friends = sorted(friends)
	for i in range(nb_friends):
		p = i % 2
		sf = sorted_friends[i]
		if d[sf][p] > 0:
			d[sf][p] -= 1
		else:
			return False
	return True

def main():
	nb_tests = int(input())
	for t in range(nb_tests):
		f_l = int(input())
		f = [int(p) for p in input().split(' ')]
		print('YES' if solve(f_l, f) else 'NO')
main()


from sys import stdin
input = lambda : stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if sorted(a)[::2] == sorted(a[::2]):
		print('YES')
	else:
		print('NO')


T = int(input())
from collections import defaultdict

def solve():
	n = int(input())
	nums = [int(x) for x in input().split()]
	arr = sorted(nums)
	d = defaultdict(int)
	for (symb, data) in ((1, nums), (-1, arr)):
		for (i, x) in enumerate(data):
			d[x] += symb if i % 2 == 0 else -symb
	for k in d:
		if d[k] != 0:
			print('NO')
			return
	print('YES')
for _ in range(T):
	solve()


import math
import sys
inp = int(input())
for _ in range(inp):
	n = int(input())
	l = list(map(int, input().split(' ')))
	odd = []
	even = []
	res = []
	for i in range(n):
		if i % 2 == 0:
			even.append(l[i])
		else:
			odd.append(l[i])
	l.sort()
	odd.sort(reverse=True)
	even.sort(reverse=True)
	for i in range(n):
		if i % 2 == 0:
			res.append(even.pop())
		else:
			res.append(odd.pop())
	if res == l:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	inds = [0 for i in range(n)]
	a = list(map(int, input().split()))
	bad = False
	asorted = sorted(a)
	arr = {i: [0, 0] for i in asorted}
	even = True
	for i in asorted:
		if even:
			arr[i][0] += 1
		else:
			arr[i][1] += 1
		even = not even
	for i in range(n):
		cur = a[i]
		possible = True
		if i % 2 == 0:
			if arr[cur][0] > 0:
				arr[cur][0] -= 1
			else:
				possible = False
		elif arr[cur][1] > 0:
			arr[cur][1] -= 1
		else:
			possible = False
		if not possible:
			print('NO')
			bad = True
			break
	if bad:
		continue
	print('YES')


from sys import stdin
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	lst = list(map(int, stdin.readline().split()))
	srt = sorted(lst)
	dic = {}
	for i in range(len(srt)):
		num = srt[i]
		if num not in dic:
			dic[num] = [0, 0]
		dic[num][i % 2] += 1
	for i in range(len(lst)):
		num = lst[i]
		dic[num][i % 2] -= 1
		if dic[num][i % 2] < 0:
			print('NO')
			break
	else:
		print('YES')


for _ in range(int(input())):
	tt = int(input())
	arr = list(map(int, input().split()))
	if tt == 1:
		print('YES')
		continue
	crr = sorted(arr)
	odl = list(arr[::2])
	evl = list(arr[1::2])
	odl.sort()
	evl.sort()
	ct1 = 0
	ct2 = 0
	flag = 1
	for x in range(tt):
		if x % 2 == 1:
			if evl[ct1] != crr[x]:
				flag = 0
				break
			ct1 += 1
		else:
			if odl[ct1] != crr[x]:
				flag = 0
				break
			ct2 += 1
	if flag:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	dp = list(map(int, input().split()))
	dp_even = [0] * (10 ** 5 + 1)
	dp_odd = [0] * (10 ** 5 + 1)
	for i in range(n):
		if i % 2 == 0:
			dp_even[dp[i]] += 1
		else:
			dp_odd[dp[i]] += 1
	dp = sorted(dp)
	for i in range(n):
		if i % 2 == 0:
			dp_even[dp[i]] -= 1
		else:
			dp_odd[dp[i]] -= 1
	flag = 0
	for i in range(n):
		if dp_odd[dp[i]] | dp_even[dp[i]]:
			print('NO')
			flag = 1
			break
	if flag == 0:
		print('YES')


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = input().split()
	a = [int(x) for x in a]
	if sorted(a)[::2] == sorted(a[::2]):
		print('YES')
	else:
		print('NO')


n = int(input())
for _n in range(n):
	t = int(input())
	a = [int(b) for b in input().split()]
	if sorted(a[::2]) == sorted(a)[::2]:
		print('YES')
	else:
		print('NO')


from collections import defaultdict as dd
from math import sqrt, log
from bisect import bisect_left, bisect_right
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = a.copy()
	s.sort()
	d = dd(list)
	d2 = dd(list)
	for i in range(n):
		d[a[i]].append(i)
		d2[s[i]].append(i)
	k1 = list(d.keys())
	k2 = list(d2.keys())
	k1.sort()
	k2.sort()
	flag = False
	for i in k1:
		arr = d[i]
		e1 = o1 = 0
		for num in arr:
			if num & 1:
				o1 += 1
			else:
				e1 += 1
		arr = d2[i]
		e2 = o2 = 0
		for num in arr:
			if num & 1:
				o2 += 1
			else:
				e2 += 1
		if e1 != e2 or o1 != o2:
			flag = True
			break
	if flag:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if sorted(arr)[::2] == sorted(arr[::2]):
		print('YES')
	else:
		print('NO')


from collections import defaultdict
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d1 = defaultdict(int)
	for j in range(n):
		if j & 1 == 0:
			d1[a[j], 0] += 1
		else:
			d1[a[j], 1] += 1
	a.sort()
	d2 = defaultdict(int)
	for j in range(n):
		if j & 1 == 0:
			d2[a[j], 0] += 1
		else:
			d2[a[j], 1] += 1
	s = set(a)
	ans = 'YES'
	for p in s:
		if d1[p, 0] != d2[p, 0] or d1[p, 1] != d2[p, 1]:
			ans = 'NO'
			break
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split(' ')]
	le = []
	lo = []
	so = []
	se = []
	a = sorted(l)
	for i in range(n):
		if i & 1:
			lo.append(l[i])
			so.append(a[i])
		else:
			le.append(l[i])
			se.append(a[i])
	le.sort()
	lo.sort()
	print('YES' if le == se and lo == so else 'NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sa = sorted(a)
	p = {}
	for i in range(n):
		if sa[i] in p:
			p[sa[i]][0] += i % 2
			p[sa[i]][1] += 1 - i % 2
		else:
			p[sa[i]] = [i % 2, 1 - i % 2]
	for i in range(n):
		if a[i] != sa[i]:
			if not p[a[i]][1 - i % 2]:
				print('NO')
				break
		p[a[i]][1 - i % 2] -= 1
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	s = input().strip().split(' ')
	a = [int(x) for x in s]
	num_of_odd_indexes = {}
	for j in range(n):
		if j % 2 == 1 and a[j] not in num_of_odd_indexes:
			num_of_odd_indexes[a[j]] = 1
		elif j % 2 == 1:
			num_of_odd_indexes[a[j]] += 1
		elif a[j] not in num_of_odd_indexes:
			num_of_odd_indexes[a[j]] = 0
	a.sort()
	possible = True
	current_index = 0
	while current_index < n:
		num_of_odd_indexes_here = 1
		if current_index % 2 == 0:
			num_of_odd_indexes_here = 0
		while current_index + 1 < n and a[current_index] == a[current_index + 1]:
			current_index += 1
			if current_index % 2 == 1:
				num_of_odd_indexes_here += 1
		if num_of_odd_indexes_here != num_of_odd_indexes[a[current_index]]:
			possible = False
		current_index += 1
	if possible:
		print('YES')
	else:
		print('NO')


(i, s) = (input, sorted)
for _ in ' ' * int(i()):
	i()
	a = [*map(int, i().split())]
	print('YNEOS'[s(a)[::2] != s(a[::2])::2])


t = int(input())
from collections import defaultdict
for i in range(t):
	n = int(input())
	lis = list(map(int, input().split()))
	dic = defaultdict(int)
	for j in range(0, len(lis)):
		if j % 2 == 0:
			dic[lis[j]] = dic[lis[j]] + 2
		else:
			dic[lis[j]] = dic[lis[j]] + 1
	dic2 = defaultdict(int)
	lis.sort()
	for j in range(0, len(lis)):
		if j % 2 == 0:
			dic2[lis[j]] = dic2[lis[j]] + 2
		else:
			dic2[lis[j]] = dic2[lis[j]] + 1
	flag = 1
	for j in dic2:
		if dic[j] != dic2[j]:
			flag = 0
			break
	if flag:
		print('YES')
	else:
		print('NO')


import sys, os.path
from typing import BinaryIO
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for t in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	l = li.copy()
	l.sort()
	di = dict()
	for i in set(l):
		di[i] = [0, 0]
	for i in range(len(li)):
		if i % 2 == 0:
			di[l[i]][0] += 1
		else:
			di[l[i]][1] += 1
	pos = 1
	for i in range(len(li)):
		if i % 2 == 0:
			if di[li[i]][0] > 0:
				di[li[i]][0] -= 1
			else:
				pos = 0
				break
		elif di[li[i]][1] > 0:
			di[li[i]][1] -= 1
		else:
			pos = 0
			break
	if pos == 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = a[:]
	a.sort()
	odd = [0 for i in range(max(a) + 1)]
	even = [0 for i in range(max(a) + 1)]
	for i in range(n):
		if i % 2 == 0:
			even[a[i]] += 1
		else:
			odd[a[i]] += 1
	a = b[:]
	flag = 1
	for i in range(n):
		if i % 2 == 0:
			if even[a[i]] == 0:
				flag = 0
			else:
				even[a[i]] -= 1
		elif odd[a[i]] == 0:
			flag = 0
		else:
			odd[a[i]] -= 1
	if flag == 0:
		print('NO')
		continue
	print('YES')


for _ in range(int(input())):
	n = int(input())
	t1 = {}
	t2 = {}
	k = [int(x) for x in input().split()]
	for i in range(n):
		if k[i] not in t1:
			t1[k[i]] = [0, 0]
		t1[k[i]][i % 2] += 1
	m = sorted(k)
	for i in range(n):
		if m[i] not in t2:
			t2[m[i]] = [0, 0]
		t2[m[i]][i % 2] += 1
	if all((t1[i] == t2[i] for i in set(k))):
		print('YES')
	else:
		print('NO')


t = int(input())
ans = []
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = sorted(a)
	f1 = [0] * (10 ** 5 + 1)
	f2 = [0] * (10 ** 5 + 1)
	for i in range(0, n, 2):
		f1[a[i]] += 1
		f2[b[i]] += 1
	if f1 == f2:
		ans.append('YES')
	else:
		ans.append('NO')
for i in ans:
	print(i)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	arr = []
	for i in range(n):
		arr.append(l[i])
	arr.sort()
	even = [0 for i in range(max(l) + 1)]
	odd = [0 for i in range(max(l) + 1)]
	for i in range(n):
		if i % 2 == 0:
			even[arr[i]] += 1
		else:
			odd[arr[i]] += 1
	flag = 1
	for i in range(n):
		if i % 2 == 0:
			if even[l[i]] == 0:
				flag = 0
			else:
				even[l[i]] -= 1
		elif odd[l[i]] == 0:
			flag = 0
		else:
			odd[l[i]] -= 1
	if flag == 0:
		print('NO')
	else:
		print('YES')


import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def test():
	n = int(input())
	l = list(map(int, input().split()))
	le = []
	lo = []
	se = []
	so = []
	s = sorted(l)
	for i in range(n):
		if i % 2 == 0:
			le.append(l[i])
			se.append(s[i])
		else:
			lo.append(l[i])
			so.append(s[i])
	le.sort()
	lo.sort()
	if le == se and lo == so:
		print('YES')
	else:
		print('NO')
t = int(input())
while t:
	test()
	t -= 1


import sys
input = sys.stdin.readline

def I():
	return input().strip()

def II():
	return int(input().strip())

def LI():
	return [*map(int, input().strip().split())]
import copy
import re
import string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict
from itertools import permutations, combinations, groupby, count, filterfalse
from operator import itemgetter
for _ in range(II()):
	n = II()
	l = LI()
	if sorted(l)[::2] == sorted(l[::2]):
		print('YES')
	else:
		print('NO')


num_cases = int(input())
for _ in range(num_cases):
	input()
	seq = [int(x) for (i, x) in enumerate(input().split(' '))]
	sum_before = {}
	possible = True
	for (i, val) in enumerate(seq):
		cur_sum = sum_before.setdefault(val, [0, 0])
		cur_sum[i % 2] += 1
		sum_before[val] = cur_sum
	seq_sorted = sorted(seq)
	for (i, val) in enumerate(seq_sorted):
		cur_sum = sum_before[val]
		cur_sum[i % 2] -= 1
		sum_before[val] = cur_sum
	for (key, val) in sum_before.items():
		if not (val[0] == 0 and val[1] == 0):
			possible = False
			break
	if possible:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p = sorted(l)
	d = dict()
	d1 = dict()
	for i in range(n):
		d.setdefault(l[i], [0, 0])
		d1.setdefault(p[i], [0, 0])
		d[l[i]][i % 2] += 1
		d1[p[i]][i % 2] += 1
	flag = True
	for (q, v) in d.items():
		if d1[q][0] != v[0] or d1[q][1] != v[1]:
			flag = False
			break
	print(['NO', 'YES'][flag])


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	f = {}
	for (index, i) in enumerate(a):
		if i not in f:
			f[i] = [0, 0]
		f[i][index % 2] += 1
	for (index, i) in enumerate(b):
		f[i][index % 2] -= 1
	check = True
	for (key, value) in f.items():
		if value[0] != 0 or value[1] != 0:
			check = False
			break
	if check:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	ans = 'NO'
	if sorted(a[::2]) == b[::2]:
		ans = 'YES'
	print(ans)


from collections import Counter
from sys import stdin, stdout
input = stdin.readline

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		a1 = sorted(a)
		p = Counter()
		for (i, v) in enumerate(a1):
			if i % 2 == 0:
				v = -v
			p[v] += 1
		for (i, v) in enumerate(a):
			if i % 2 == 0:
				v = -v
			if p[v] > 0:
				p[v] -= 1
			else:
				print('NO')
				break
		else:
			print('YES')
main()


def func():
	init = dict()
	final = dict()
	for (i, j) in enumerate(a):
		if j in init:
			init[j][i % 2] += 1
		else:
			init[j] = [0, 0]
			init[j][i % 2] += 1
	a.sort()
	for (i, j) in enumerate(a):
		if j in final:
			final[j][i % 2] += 1
		else:
			final[j] = [0, 0]
			final[j][i % 2] += 1
	for i in init:
		if init[i] != final[i]:
			print('NO')
			return
	print('YES')
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	func()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if sorted(a)[::2] == sorted(a[::2]):
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline
from collections import defaultdict

def main():
	n = int(input())
	alst = list(map(int, input().split()))
	dd_odd = defaultdict(int)
	dd_even = defaultdict(int)
	for (i, a) in enumerate(alst):
		if i % 2 == 0:
			dd_even[a] += 1
		else:
			dd_odd[a] += 1
	alst.sort()
	for (i, a) in enumerate(alst):
		if i % 2 == 0:
			if dd_even[a] == 0:
				print('NO')
				return
			dd_even[a] -= 1
		else:
			if dd_odd[a] == 0:
				print('NO')
				return
			dd_odd[a] -= 1
	print('YES')
for _ in range(int(input())):
	main()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ls = l.copy()
	ls.sort()
	dic = dict()
	for i in range(n):
		if ls[i] in dic:
			if i % 2 == 1:
				dic[ls[i]][0] += 1
			else:
				dic[ls[i]][1] += 1
		elif i % 2 == 1:
			dic[ls[i]] = [1, 0]
		else:
			dic[ls[i]] = [0, 1]

	def f():
		for i in range(n):
			if i % 2 == 1:
				if dic[l[i]][0] > 0:
					dic[l[i]][0] -= 1
				else:
					return False
			elif dic[l[i]][1] > 0:
				dic[l[i]][1] -= 1
			else:
				return False
		return True
	if f():
		print('YES')
	else:
		print('NO')


import sys
import math
import bisect
import heapq
from bisect import bisect_right
from sys import stdin, stdout

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(sys.stdin.readline())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def myceil(x, y):
	return (x + y - 1) // y

def Solution(arr, n):
	limit = pow(10, 5) + 1
	dp = [[0 for _ in range(limit)] for _ in range(2)]
	flg = True
	for i in range(n):
		dp[i % 2][arr[i]] += 1
	arr = sorted(arr)
	for i in range(n):
		dp[i % 2][arr[i]] -= 1
	for i in range(limit):
		for j in range(2):
			if dp[j][i] > 0:
				flg = False
				break
	if flg:
		print('YES')
	else:
		print('NO')

def main():
	for _ in range(get_int()):
		n = get_int()
		arr = get_ints_in_list()
		Solution(arr, n)
main()


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	s = sorted(arr)
	v = {}
	for i in range(n):
		if arr[i] in v:
			v[arr[i]][i % 2] += 1
		else:
			v[arr[i]] = [0, 0]
			v[arr[i]][i % 2] += 1
	ans = 'YES'
	flag = False
	i = -1
	while not flag:
		i += 1
		if v[s[i]][i % 2] != 0:
			v[s[i]][i % 2] -= 1
		else:
			flag = True
			ans = 'NO'
		if i + 1 == n:
			flag = True
	print(ans)


def strangesort(n, arr):
	tab = [(arr[i], i) for i in range(n)]
	tab = sorted(tab, key=lambda x: x[0])
	cur_count = [0, 0]
	prev = -1
	for x in range(n):
		if tab[x][0] != prev:
			if cur_count[0] != cur_count[1]:
				print('NO')
				return
			cur_count[0] = 0
			cur_count[1] = 0
		prev = tab[x][0]
		cur_count[x % 2] += abs(x - tab[x][1]) & 1
	print('YES')
for _ in range(int(input())):
	strangesort(int(input()), list(map(int, input().split())))


import sys
LI = lambda : list(map(int, sys.stdin.readline().split()))
MI = lambda : map(int, sys.stdin.readline().split())
SI = lambda : sys.stdin.readline().strip('\n')
II = lambda : int(sys.stdin.readline())
for _ in range(II()):
	n = II()
	a = LI()
	s = sorted(a)
	t1 = {}
	t2 = {}
	for (i, v) in enumerate(a):
		try:
			t1[v].append(i)
		except:
			t1[v] = [i]
	for (i, v) in enumerate(s):
		try:
			t2[v].append(i)
		except:
			t2[v] = [i]
	ok = 1
	for v in t1:
		if abs(sum((c % 2 for c in t1[v])) - sum((c % 2 for c in t2[v]))):
			ok = 0
	print(['NO', 'YES'][ok])


from collections import defaultdict

def readline():
	return map(int, input().split())
t = int(input())
for __ in range(t):
	n = int(input())
	a = sorted(((v, i) for (i, v) in enumerate(readline())))
	inv = defaultdict(int)
	for (i, (v, j)) in enumerate(a):
		inv[v] += (i & 1) - (j & 1)
	print('NO' if any(inv.values()) else 'YES')


def pro(arr):
	dic = {}
	n = len(arr)
	for i in range(n):
		if arr[i] in dic:
			if i % 2 == 0:
				dic[arr[i]][0] += 1
			else:
				dic[arr[i]][1] += 1
		elif i % 2 == 0:
			dic[arr[i]] = [1, 0]
		else:
			dic[arr[i]] = [0, 1]
	arr.sort()
	dic2 = {}
	n = len(arr)
	for i in range(n):
		if arr[i] in dic2:
			if i % 2 == 0:
				dic2[arr[i]][0] += 1
			else:
				dic2[arr[i]][1] += 1
		elif i % 2 == 0:
			dic2[arr[i]] = [1, 0]
		else:
			dic2[arr[i]] = [0, 1]
	for (i, j) in dic2.items():
		if dic[i] != j:
			print('NO')
			return
	print('YES')
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	pro(arr)


import bisect

def solve(t_id):
	n = int(input())
	a = list(map(int, input().split()))
	b = [a[i] for i in range(n)]
	ok = True
	ind1 = {}
	ind2 = {}
	b.sort()
	for i in range(n):
		if i % 2 == 0:
			if b[i] in ind2:
				ind2[b[i]].append(i)
			else:
				ind2[b[i]] = [i]
		elif b[i] in ind1:
			ind1[b[i]].append(i)
		else:
			ind1[b[i]] = [i]
	for i in range(n):
		if i % 2 == 0 and a[i] in ind2 and (len(ind2[a[i]]) > 0):
			ind2[a[i]].pop(0)
		elif i % 2 == 1 and a[i] in ind1 and (len(ind1[a[i]]) > 0):
			ind1[a[i]].pop(0)
		else:
			ok = False
			break
	print('YES' if ok else 'NO')
t = 1
t = int(input())
for i in range(t):
	solve(i + 1)


import os
import sys
from math import *
from collections import *
from itertools import *
from heapq import *
from bisect import *
from io import BytesIO, IOBase
from typing import overload

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 998244353
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
for _ in range(Int()):
	n = Int()
	a = array()
	n = len(a)
	ans = 'YES'
	ind = defaultdict(lambda : [0, 0])
	for i in range(n):
		ind[a[i]][i % 2] += 1
	a = sorted(a)
	for i in range(n):
		if ind[a[i]][i % 2] <= 0:
			ans = 'NO'
		ind[a[i]][i % 2] -= 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(o, e) = ([], [])
	for i in range(n):
		if i % 2 == 0:
			e.append(a[i])
		else:
			o.append(a[i])
	a.sort()
	o.sort()
	e.sort()
	p = 0
	q = 0
	flag = 1
	for i in range(n):
		if i % 2 == 0:
			if e[p] == a[i]:
				p += 1
				pass
			else:
				flag = 0
				break
		elif o[q] == a[i]:
			q += 1
			pass
		else:
			flag = 0
			break
	if flag:
		print('YES')
	else:
		print('NO')


def putin():
	return map(int, input().split())

def sol():
	n = int(input())
	A = list(putin())
	Count1 = [0] * 10 ** 5
	Count2 = [0] * 10 ** 5
	for (i, elem) in enumerate(A):
		if i % 2 == 0:
			Count1[elem - 1] += 1
		else:
			Count2[elem - 1] += 1
	cnt = 0
	i = 0
	while i < 10 ** 5:
		if cnt == 0:
			if Count1[i] > 0:
				Count1[i] -= 1
				cnt = 1
			elif Count2[i] > 0:
				return 'NO'
			else:
				i += 1
		if cnt == 1:
			if Count2[i] > 0:
				Count2[i] -= 1
				cnt = 0
			elif Count1[i] > 0:
				return 'NO'
			else:
				i += 1
	return 'YES'
for itr in range(int(input())):
	print(sol())


from collections import *
for _ in range(int(input())):
	n = int(input())
	ai = list(map(int, input().split()))
	ais = list(sorted(ai))
	indo = defaultdict(list)
	inde = defaultdict(list)
	for i in range(n - 1, -1, -1):
		if not i % 2:
			inde[ais[i]].append(i)
		else:
			indo[ais[i]].append(i)
	for i in range(n):
		if i % 2:
			if len(indo[ai[i]]) == 0:
				print('NO')
				break
			else:
				indo[ai[i]].pop()
		elif len(inde[ai[i]]) == 0:
			print('NO')
			break
		else:
			inde[ai[i]].pop()
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().rstrip().split()))
	dodd = {}
	deven = {}
	d1 = {}
	d2 = {}
	for i in range(n):
		if i % 2 == 0:
			if arr[i] in deven.keys():
				deven[arr[i]] += 1
			else:
				deven[arr[i]] = 1
		elif arr[i] in dodd.keys():
			dodd[arr[i]] += 1
		else:
			dodd[arr[i]] = 1
	arr.sort()
	for i in range(n):
		if i % 2 == 0:
			if arr[i] in d1.keys():
				d1[arr[i]] += 1
			else:
				d1[arr[i]] = 1
		elif arr[i] in d2.keys():
			d2[arr[i]] += 1
		else:
			d2[arr[i]] = 1
	if d1 == deven and d2 == dodd:
		print('YES')
	else:
		print('NO')


import math
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ae = []
	ao = []
	for i in range(n):
		if i % 2 == 0:
			ae.append(arr[i])
		else:
			ao.append(arr[i])
	ao.sort()
	ae.sort()
	arr3 = []
	arr.sort()
	flag = True
	p1 = 0
	p2 = 0
	for kk in range(n):
		if kk % 2 == 0:
			if arr[kk] == ae[p1]:
				flag = True
			else:
				flag = False
				break
			p1 += 1
		else:
			if arr[kk] == ao[p2]:
				flag = True
			else:
				flag = False
				break
			p2 += 1
	if flag:
		print('YES')
	else:
		print('NO')


for _ in range(int(input().strip())):
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	flag = 0
	c = max(arr)
	cnt = [[0, 0] for i in range(c + 1)]
	for i in range(0, n):
		cnt[arr[i]][i % 2] += 1
	arr.sort()
	for i in range(0, n):
		cnt[arr[i]][i % 2] -= 1
	for i in range(n):
		if cnt[arr[i]][0] != 0 or cnt[arr[i]][1] != 0:
			print('NO')
			flag = 1
			break
	if flag == 0:
		print('YES')


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.buffer.readline
	for _ in range(int(input())):
		N = int(input())
		A = list(map(int, input().split()))
		IA = [(i, a) for (i, a) in enumerate(sorted(A))]
		cnt = {}
		for (i, a) in IA:
			if a in cnt:
				cnt[a][i & 1] += 1
			else:
				cnt[a] = [0, 0]
				cnt[a][i & 1] += 1
		cnt_ori = {}
		for (i, a) in enumerate(A):
			if a in cnt_ori:
				cnt_ori[a][i & 1] += 1
			else:
				cnt_ori[a] = [0, 0]
				cnt_ori[a][i & 1] += 1
		ok = 1
		for a in cnt:
			if cnt[a] != cnt_ori[a]:
				ok = 0
				break
		if ok:
			print('YES')
		else:
			print('NO')
main()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	ea = []
	oa = []
	eb = []
	ob = []
	for j in range(0, n, 2):
		ea.append(a[j])
	for j in range(1, n, 2):
		oa.append(a[j])
	for j in range(0, n, 2):
		eb.append(b[j])
	for j in range(1, n, 2):
		ob.append(b[j])
	ea.sort()
	oa.sort()
	if ea == eb and oa == ob:
		print('YES')
	else:
		print('NO')


import sys
import math
import collections
import heapq
import decimal
input = sys.stdin.readline
t = int(input())
for w in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	l1 = sorted(l)
	odd1 = []
	odd2 = []
	eve1 = []
	eve2 = []
	for i in range(n):
		if i % 2 == 0:
			eve1.append(l[i])
			eve2.append(l1[i])
		else:
			odd1.append(l[i])
			odd2.append(l1[i])
	d1 = collections.Counter(eve1)
	d2 = collections.Counter(eve2)
	d3 = collections.Counter(odd1)
	d4 = collections.Counter(odd2)
	if d1 == d2 and d3 == d4:
		print('YES')
	else:
		print('NO')


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	res = []
	d = defaultdict(lambda : [0, 0])
	for i in range(n):
		if i % 2 == 0:
			d[A[i]][0] += 1
		else:
			d[A[i]][1] += 1
	A.sort()
	d2 = defaultdict(lambda : [0, 0])
	for i in range(n):
		if i % 2 == 0:
			d2[A[i]][0] += 1
		else:
			d2[A[i]][1] += 1
	ok = True
	for i in d.keys():
		if d[i][0] != d2[i][0]:
			ok = False
	if ok:
		print('YES')
	else:
		print('NO')


from collections import deque, defaultdict, Counter
from itertools import product, groupby, permutations, combinations, accumulate
from math import gcd, floor, inf, log2, sqrt, log10
from bisect import bisect_right, bisect_left
from statistics import mode

def solve(array):
	st = defaultdict(deque)
	for (i, n) in enumerate(array):
		if i % 2:
			st[n].appendleft(1)
		else:
			st[n].append(0)
	return st
cases = int(input())
for _ in range(cases):
	num = int(input())
	arr = list(map(int, input().split()))
	sor = sorted(arr)
	if solve(arr) == solve(sor):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dp = [0 for x in range(10 ** 5 + 2)]
	for i in range(n):
		if i % 2 == 0:
			dp[a[i]] += 1
	a.sort()
	for i in range(n):
		if i % 2 == 0:
			dp[a[i]] -= 1
	flag = True
	for k in dp:
		if k != 0:
			flag = False
			break
	if flag:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline
from collections import Counter
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	B = sorted(A)
	od = Counter()
	ev = Counter()
	for (i, b) in enumerate(B):
		if i % 2:
			od[b] += 1
		else:
			ev[b] += 1
	for (i, a) in enumerate(A):
		if i % 2:
			if od[a] <= 0:
				print('NO')
				break
			else:
				od[a] -= 1
		elif ev[a] <= 0:
			print('NO')
			break
		else:
			ev[a] -= 1
	else:
		print('YES')


import heapq
answers = []

def solve(n, arr):
	odd = []
	even = []
	for i in range(0, n, 2):
		even.append(arr[i])
	for i in range(1, n, 2):
		odd.append(arr[i])
	i = 0
	j = 0
	even.sort()
	odd.sort()
	arr.sort()
	for k in range(n):
		if k % 2 == 0:
			if arr[k] != even[i]:
				print('NO')
				return
			i += 1
		else:
			if arr[k] != odd[j]:
				print('NO')
				return
			j += 1
	print('YES')
	return
T = int(input())
while T:
	n = int(input())
	arr = [int(x) for x in input().split()]
	solve(n, arr)
	T -= 1
for ans in answers:
	print(ans)


for _ in range(int(input())):
	i = int(input())
	l = list(map(int, input().split()))
	print('YES' if sorted(l[::2]) == sorted(l)[::2] else 'NO')


T = int(input())
for TT in range(T):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = a[:]
	b.sort()
	odd = {}
	even = {}
	for i in range(len(a)):
		if i % 2 == 0:
			if a[i] not in even:
				even[a[i]] = 0
			even[a[i]] += 1
			if b[i] not in even:
				even[b[i]] = 0
			even[b[i]] -= 1
		else:
			if a[i] not in odd:
				odd[a[i]] = 0
			odd[a[i]] += 1
			if b[i] not in odd:
				odd[b[i]] = 0
			odd[b[i]] -= 1
	ans = True
	for i in range(len(a)):
		flag = (a[i] not in odd or odd[a[i]] == 0) and (a[i] not in even or even[a[i]] == 0)
		if flag == False:
			ans = False
			break
	print('YES' if ans else 'NO')


def solve(n, arr):
	pos1 = [[] for i in range(10 ** 5 + 1)]
	for (i, a) in enumerate(arr):
		pos1[a].append(i)
	pos2 = [[] for i in range(10 ** 5 + 1)]
	arr.sort()
	for (i, a) in enumerate(arr):
		pos2[a].append(i)
	for i in range(1, 10 ** 5 + 1):
		c = 0
		for a in pos1[i]:
			c += a & 1
		for a in pos2[i]:
			c -= a & 1
		if c:
			return False
	return True
import sys
input = lambda : sys.stdin.readline().rstrip()
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(['NO', 'YES'][solve(n, arr)])