You are given three arrays $a$, $b$ and $c$. Initially, array $a$ consists of $n$ elements, arrays $b$ and $c$ are empty.

You are performing the following algorithm that consists of two steps:

Step $1$: while $a$ is not empty, you take the last element from $a$ and move it in the middle of array $b$. If $b$ currently has odd length, you can choose: place the element from $a$ to the left or to the right of the middle element of $b$. As a result, $a$ becomes empty and $b$ consists of $n$ elements.

Step $2$: while $b$ is not empty, you take the middle element from $b$ and move it to the end of array $c$. If $b$ currently has even length, you can choose which of two middle elements to take. As a result, $b$ becomes empty and $c$ now consists of $n$ elements.

Refer to the Note section for examples.

Can you make array $c$ sorted in non-decreasing order?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Next $t$ cases follow.

The first line of each test case contains the single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — the array $a$ itself.

It's guaranteed that the sum of $n$ doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test, print YES (case-insensitive), if you can make array $c$ sorted in non-decreasing order. Otherwise, print NO (case-insensitive).


-----Examples-----

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


-----Note-----

In the first test case, we can do the following for $a = [3, 1, 5, 3]$:

Step $1$:

$a$

$[3, 1, 5, 3]$

$\Rightarrow$

$[3, 1, 5]$

$\Rightarrow$

$[3, 1]$

$\Rightarrow$

$[3]$

$\Rightarrow$

$[]$

$b$

$[]$

$[\underline{3}]$

$[3, \underline{5}]$

$[3, \underline{1}, 5]$

$[3, \underline{3}, 1, 5]$

Step $2$:

$b$

$[3, 3, \underline{1}, 5]$

$\Rightarrow$

$[3, \underline{3}, 5]$

$\Rightarrow$

$[\underline{3}, 5]$

$\Rightarrow$

$[\underline{5}]$

$\Rightarrow$

$[]$

$c$

$[]$

$[1]$

$[1, 3]$

$[1, 3, 3]$

$[1, 3, 3, 5]$

As a result, array $c = [1, 3, 3, 5]$ and it's sorted.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Implementation

Constructive algorithms


Solutions:
import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	b = sorted(a)
	for i in range(n % 2, n, 2):
		if not (a[i] == b[i] and a[i + 1] == b[i + 1] or (a[i] == b[i + 1] and a[i + 1] == b[i])):
			print('NO')
			return
	print('YES')

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


input = open(0).readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(len(a) % 2, len(a) - 1, 2):
		if a[i] > a[i + 1]:
			(a[i], a[i + 1]) = (a[i + 1], a[i])
	if a == list(sorted(a)):
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline

def solve():
	N = int(input())
	a = list(map(int, input().split()))
	for i in range(N - 2, -1, -2):
		if a[i] > a[i + 1]:
			(a[i], a[i + 1]) = (a[i + 1], a[i])
	for i in range(N - 1):
		if a[i] > a[i + 1]:
			print('NO')
			return
	print('YES')
T = int(input())
for _ in range(T):
	solve()


for arr in map(lambda s: list(map(int, s.split())), [*open(0)][2::2]):
	n = len(arr)
	flag = 0
	x = 0
	index = 0
	if n & 1:
		x = arr[0]
		index = 1
	for i in range(index, n, 2):
		if arr[i] < x or arr[i + 1] < x:
			flag = 1
			break
		x = max(arr[i], arr[i + 1])
	print(['YES', 'NO'][flag])


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


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = sorted(l)
	if n % 2 == 0:
		for i in range(0, n - 1, 2):
			if l[i] == a[i] and l[i + 1] == a[i + 1]:
				continue
			elif l[i] == a[i + 1] and l[i + 1] == a[i]:
				continue
			else:
				print('NO')
				break
		else:
			print('YES')
	elif a[0] != l[0]:
		print('NO')
	else:
		for i in range(1, n - 1, 2):
			if l[i] == a[i] and l[i + 1] == a[i + 1]:
				continue
			elif l[i] == a[i + 1] and l[i + 1] == a[i]:
				continue
			else:
				print('NO')
				break
		else:
			print('YES')


import sys
input = sys.stdin.readline

def sol(n, data):
	if n % 2 == 1:
		data = [0] + data
	arr = [(data[i], data[i + 1]) for i in range(0, n - 1, 2)]
	data.sort()
	for (i, (a, b)) in enumerate(arr):
		temp = (data[i * 2], data[i * 2 + 1])
		if not ((a, b) == temp or (b, a) == temp):
			return False
	return True
T = int(input())
for _ in range(T):
	n = int(input())
	data = list(map(int, input().split()))
	ret = sol(n, data)
	if ret:
		print('YES')
	else:
		print('NO')


def value(array):
	len_a = len(array)
	if len_a % 2 != 0:
		max_a = array[0]
		start_i = 1
	else:
		max_a = max(array[0], array[1])
		start_i = 2
	for i in range(start_i, len_a, 2):
		temp_min = min(array[i], array[i + 1])
		if temp_min < max_a:
			return 'NO'
		max_a = max(array[i], array[i + 1])
	return 'YES'

def main():
	n = int(input())
	data = []
	for i in range(n):
		k = input()
		array = list(map(int, input().split()))
		data.append(array)
	for array in data:
		print(value(array))
main()


import sys

def fn(a, l):
	if l % 2 == 0:
		prev = 1000001
		for i in range(l, 0, -2):
			(curr_1, curr_2) = (a[i - 1], a[i - 2])
			if max(curr_1, curr_2) > prev:
				return 'NO'
			prev = min(curr_1, curr_2)
	else:
		prev = 1000001
		for i in range(l, 1, -2):
			(curr_1, curr_2) = (a[i - 1], a[i - 2])
			if max(curr_1, curr_2) > prev:
				return 'NO'
			prev = min(curr_1, curr_2)
		if a[0] > prev:
			return 'NO'
	return 'YES'
input = sys.stdin.readlines()
for i in range(int(input[0].strip('\n'))):
	len_list = int(input[2 * i + 1].strip('\n'))
	new_list = [int(x) for x in input[2 * i + 2].strip('\n').split(' ')]
	out = fn(new_list, len_list)
	print(out)


t = int(input())
out = ''
for _ in range(t):
	size = int(input())
	arr = [int(x) for x in input().split()]
	arr.reverse()
	if len(arr) <= 2:
		out += 'YES\n'
		continue
	min_ = min(arr[0], arr[1])
	for i in range(2, len(arr) - 1, 2):
		if max(arr[i], arr[i + 1]) > min_:
			out += 'NO\n'
			break
		min_ = min(arr[i], arr[i + 1])
	else:
		if len(arr) % 2 == 1 and arr[-1] > min_:
			out += 'NO\n'
		else:
			out += 'YES\n'
print(out)


import sys

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

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

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

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

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

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')

def solve():
	for _ in range(get_int()):
		n = get_int()
		arr = get_list()
		sarr = sorted(arr)
		ln = n
		start = 0
		ans = 'YES'
		(p1, p2) = (None, None)
		if ln % 2 == 0:
			p1 = 0
			p2 = 1
		else:
			p1 = 0
			p2 = 0
		while start < n:
			if ln % 2 == 0:
				if arr[p1] != sarr[start] and arr[p2] != sarr[start]:
					ans = 'NO'
					break
				elif arr[p1] == sarr[start]:
					p1 = p2
				else:
					p1 = p1
			else:
				if arr[p1] != sarr[start]:
					ans = 'NO'
					break
				p1 = p2 + 1
				p2 = p1 + 1
			ln -= 1
			start += 1
		get_print(ans)
solve()


from sys import stdin, stdout
from collections import defaultdict
input = stdin.readline
from random import randint
import math
import sys
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	if n % 2 == 0:
		i = 0
		while i < n and i + 1 < n:
			if a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
			i += 2
	else:
		i = 1
		while i < n and i + 1 < n:
			if a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
			i += 2
	if a == b:
		print('YES')
	else:
		print('NO')


def Solve():
	(ns, A) = ([], [])
	for t in range(int(input())):
		ns.append(int(input()))
		A.append(list(map(int, input().split())))
	for (n, a) in zip(ns, A):
		sa = sorted(a)
		if n % 2 == 0:
			for i in range(n):
				if i % 2 != 0:
					if a[i] == sa[i]:
						a[i] = 0
					elif a[i - 1] == sa[i]:
						a[i - 1] = 0
					else:
						print('NO')
						break
				elif a[i] == sa[i]:
					a[i] = 0
				elif a[i + 1] == sa[i]:
					a[i + 1] = 0
				else:
					print('NO')
					break
			else:
				print('YES')
		else:
			for i in range(n):
				if i % 2 == 0:
					if a[i] == sa[i]:
						a[i] = 0
					elif a[i - 1] == sa[i]:
						a[i - 1] = 0
					else:
						print('NO')
						break
				elif a[i] == sa[i]:
					a[i] = 0
				elif a[i + 1] == sa[i]:
					a[i + 1] = 0
				else:
					print('NO')
					break
			else:
				print('YES')
Solve()


import sys
from collections import *
sys.setrecursionlimit(10 ** 5)
itr = (line for line in sys.stdin.read().strip().split('\n'))
INP = lambda : next(itr)

def ni():
	return int(INP())

def nl():
	return [int(_) for _ in INP().split()]

def solve(n, arr):
	c = [0 for _ in range(n)]
	start = 0
	if n % 2 != 0:
		c[0] = arr[0]
		start = 1
	for i in range(start, n - 1, 2):
		if arr[i] < arr[i + 1]:
			c[i] = arr[i]
			c[i + 1] = arr[i + 1]
		else:
			c[i] = arr[i + 1]
			c[i + 1] = arr[i]
	for i in range(1, n):
		if c[i - 1] > c[i]:
			return 'NO'
	return 'YES'
t = ni()
for case in range(t):
	n = ni()
	arr = nl()
	print(solve(n, arr))


def sort(l, array):
	if l % 2 == 0:
		i = 0
		while i <= l - 2:
			if array[i] > array[i + 1]:
				(array[i], array[i + 1]) = (array[i + 1], array[i])
			i += 2
	else:
		i = 1
		while i <= l - 2:
			if array[i] > array[i + 1]:
				(array[i], array[i + 1]) = (array[i + 1], array[i])
			i += 2
	i = 0
	while i <= l - 2:
		if array[i] > array[i + 1]:
			return 'NO'
		i += 1
	return 'YES'
t = int(input())
li = []
for _ in range(t):
	li.append([int(input()), [int(i) for i in input().split()]])
for i in li:
	print(sort(i[0], i[1]))


import sys
import math
T = int(input())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	ans = True
	prev = math.inf
	for i in range(N - 1, -1, -2):
		if i == 0:
			now = A[i]
			mini = A[i]
		else:
			now = max(A[i], A[i - 1])
			mini = min(A[i], A[i - 1])
		if now <= prev:
			prev = mini
		else:
			ans = False
			break
	print('YES' if ans else 'NO')


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	used = [0] * n
	itr = 0
	res = []
	len = n
	while len != 0 and itr < n:
		if used[itr]:
			itr += 1
		if len & 1 or a[itr] <= a[itr + 1]:
			res.append(a[itr])
			used[itr] = 1
			itr += 1
		else:
			res.append(a[itr + 1])
			used[itr + 1] = 1
		len -= 1
	return res == sorted(a)
for _ in range(int(input())):
	print(('NO', 'YES')[solve()])


def task():
	n = int(input())
	s = str(input())
	a = s.split(' ')[:n]
	if n % 2 == 1:
		prev_max = int(a[0])
		start = 1
	else:
		prev_max = 0
		start = 0
	for i in range(start, n, 2):
		curr_min = min(int(a[i]), int(a[i + 1]))
		if curr_min < prev_max:
			return 'NO'
		prev_max = max(int(a[i]), int(a[i + 1]))
	return 'YES'

def main():
	n = int(input())
	answers = []
	for _ in range(n):
		answers.append(task())
	for ans in answers:
		print(ans)
main()


t = int(input())
inp = []
for a in range(0, t):
	input()
	inp.append([int(x) for x in input().split()])

def logic(arr):
	n = len(arr)
	if n <= 2:
		return 'YES'
	bound = min(arr[-2:])
	for j in range(-2, -n, -2):
		sec = arr[j - 2:j]
		if max(sec) <= bound:
			bound = min(sec)
		else:
			return 'NO'
	return 'YES'
for arr in inp:
	print(logic(arr))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	c = sorted(a)
	x = 0
	if n % 2 == 1:
		if a[0] != c[0]:
			print('NO')
			x = n + 2
		else:
			n = n - 1
			a.pop(0)
			c.pop(0)
	p = n // 2
	while x < p:
		if sorted([a[2 * x], a[2 * x + 1]]) != [c[2 * x], c[2 * x + 1]]:
			print('NO')
			x = p + 1
		else:
			x = x + 1
	if x == p:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n % 2, n, 2):
		if a[i] > a[i + 1]:
			temp = a[i]
			a[i] = a[i + 1]
			a[i + 1] = temp
	ans = True
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			ans = False
			break
	if ans:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	for i in range(n % 2, n, 2):
		if a[i] > a[i + 1]:
			(a[i], a[i + 1]) = (a[i + 1], a[i])
	print('YES' if a == sorted(a) else 'NO')


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	for i in range(n - 2, -1, -2):
		if A[i] > A[i + 1]:
			(A[i], A[i + 1]) = (A[i + 1], A[i])
	print('YES' if A == sorted(A) else 'NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n <= 2:
		print('YES')
		continue
	ans = 'YES'
	s = list(a)
	s.sort()
	if n % 2 == 1 and s[0] != a[0]:
		print('NO')
		continue
	for i in range(len(a) - 1, 0, -2):
		if a[i] == s[i] and a[i - 1] == s[i - 1]:
			continue
		elif a[i - 1] == s[i] and a[i] == s[i - 1]:
			continue
		else:
			ans = 'NO'
			break
	print(ans)


for _ in range(int(input())):
	(n, l) = (int(input()), list(map(int, input().split())))
	for x in range(n - 1, 0, -2):
		if l[x] < l[x - 1]:
			(l[x], l[x - 1]) = (l[x - 1], l[x])
	if l == sorted(l):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = sorted(l)
	isPossible = True
	if l == s:
		print('YES')
	elif n >= 2:
		for i in range(n - 1, 1, -2):
			if not (l[i] == s[i] and l[i - 1] == s[i - 1] or (l[i - 1] == s[i] and l[i] == s[i - 1])):
				print('NO')
				isPossible = False
				break
		if isPossible:
			print('YES')


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	vec = list(map(int, input().split()))
	for i in range(n - 1, 0, -2):
		if vec[i - 1] > vec[i]:
			(vec[i - 1], vec[i]) = (vec[i], vec[i - 1])
	print('YES' if sorted(vec) == vec else 'NO')


def solve(n, a):
	if n <= 2:
		return 'YES'
	s = 0
	if n % 2:
		s = a[0]
		a = a[1:]
	for i in range(0, len(a), 2):
		if a[i] < s or a[i + 1] < s:
			return 'NO'
		else:
			s = max(a[i], a[i + 1])
	else:
		return 'YES'
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(n, a))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l2 = sorted(l)
	now = 0
	if n % 2 == 0:
		while now < n - 1:
			if l[now] != l2[now]:
				(l[now], l[now + 1]) = (l[now + 1], l[now])
			now += 2
	else:
		now = 1
		while now < n - 1:
			if l[now] != l2[now]:
				(l[now], l[now + 1]) = (l[now + 1], l[now])
			now += 2
	print('YES' if l == l2 else 'NO')


def issorted(a):
	for i in range(len(a) - 1):
		if a[i] <= a[i + 1]:
			continue
		else:
			return False
	return True
t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	i = len(a) - 1
	while i > 0:
		if a[i] >= a[i - 1]:
			pass
		else:
			(a[i], a[i - 1]) = (a[i - 1], a[i])
		i -= 2
	if issorted(a):
		print('YES')
	else:
		print('NO')


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	sarr = sorted(arr)
	if n == 1:
		return 'YES'
	if n % 2:
		if arr[0] != sarr[0]:
			return 'NO'
		arr.pop(0)
		sarr.pop(0)
		n -= 1
	i = 0
	while i < n:
		if arr[i] != sarr[i]:
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		if arr[i] != sarr[i]:
			return 'NO'
		if arr[i + 1] != sarr[i + 1]:
			return 'NO'
		i += 2
	return 'YES'
for _ in range(int(input())):
	print(main())


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for j in range(n - 1, 0, -2):
		if a[j - 1] > a[j]:
			(a[j - 1], a[j]) = (a[j], a[j - 1])
	if a == sorted(a):
		print('YES')
	else:
		print('NO')


def cal(l):
	s = sorted(l)
	if len(l) % 2 == 1:
		if l[0] != s[0]:
			return 'NO'
		for j in range(1, len(l), 2):
			if l[j] == s[j] and l[j + 1] == s[j + 1] or (l[j] == s[j + 1] and l[j + 1] == s[j]):
				continue
			else:
				return 'NO'
	else:
		for j in range(0, len(l), 2):
			if l[j] == s[j] and l[j + 1] == s[j + 1] or (l[j] == s[j + 1] and l[j + 1] == s[j]):
				continue
			else:
				return 'NO'
	return 'YES'
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split(' ')))
	print(cal(l))


def solution():
	n = int(input())
	arr = list(map(int, input().split()))
	i = 0
	while i < n:
		if (n - i) % 2 == 0:
			if i + 1 != n and arr[i] > arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		i += 1
	for i in range(1, n):
		if arr[i] < arr[i - 1]:
			print('NO')
			return
	print('YES')

def main():
	T = int(input())
	for t in range(1, T + 1):
		solution()
main()


import sys
msg = sys.stdin.readlines()

def change(lst):
	res = []
	if len(lst) % 2:
		res.append(lst[0])
		lst = lst[1:]
	for i in range(len(lst) // 2):
		res.append(min(lst[2 * i], lst[2 * i + 1]))
		res.append(max(lst[2 * i], lst[2 * i + 1]))
	return res

def check(lst):
	if lst == sorted(lst):
		return True
	else:
		return False
for i in range(2, 2 * int(msg[0]) + 1, 2):
	lsg = msg[i].split()
	lista = list(map(int, lsg))
	if len(lista) == 1:
		print('YES')
		continue
	lista = change(lista)
	if check(lista):
		print('YES')
	else:
		print('NO')


def main():
	test = int(input())
	while test:
		test -= 1
		n = int(input())
		a = []
		a.append(0)
		for x in input().split():
			a.append(int(x))
		ok = n % 2
		for i in range(1, n):
			if ok == 0:
				if a[i] > a[i + 1]:
					tmp = a[i]
					a[i] = a[i + 1]
					a[i + 1] = tmp
				ok = 1
			else:
				ok = 0
		ok = 0
		for i in range(1, n):
			if a[i] > a[i + 1]:
				ok = 1
				break
		if ok == 1:
			print('NO')
		else:
			print('YES')
main()


def solution():
	n = int(input())
	a = [int(i) for i in input().split()]
	for i in range(n % 2, n, 2):
		a[i:i + 2] = sorted(a[i:i + 2])
	if a == sorted(a):
		return 'YES'
	return 'NO'
t = int(input())
for _ in range(t):
	print(solution())


def ff(a, b):
	while len(a) > 0:
		n = len(a)
		if n % 2 != 0:
			b.append(a[n // 2])
			a.pop(n // 2)
		else:
			ind = n // 2
			if ind == 0:
				b.append(a[ind])
				a.pop(ind)
			elif a[ind] < a[ind - 1]:
				b.append(a[ind])
				a.pop(ind)
			else:
				b.append(a[ind - 1])
				a.pop(ind - 1)

def f(a, b):
	for i in range(len(a) - 1, -1, -1):
		ele = a[i]
		n = len(b)
		if n % 2 == 0:
			b.insert(n // 2, ele)
		else:
			tm = b[n // 2]
			if ele > tm:
				b.insert(n // 2 + 1, ele)
			else:
				b.insert(n // 2 - 1, ele)

def fr(st):
	d = {}
	for ele in st:
		d[ele] = d.get(ele, 0) + 1
	return d
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	c = []
	for i in range(n % 2, n - 1, 2):
		if a[i] > a[i + 1]:
			(a[i], a[i + 1]) = (a[i + 1], a[i])
	if a == sorted(a):
		print('YES')
	else:
		print('NO')


import math

def ans(arr):
	if len(arr) % 2 == 0:
		i = 0
		j = 1
		while j <= len(arr) - 1:
			if arr[i] > arr[j]:
				temp = arr[j]
				arr[j] = arr[i]
				arr[i] = temp
			i = i + 2
			j = j + 2
	else:
		i = 1
		j = 2
		while j <= len(arr) - 1:
			if arr[i] > arr[j]:
				temp = arr[j]
				arr[j] = arr[i]
				arr[i] = temp
			i = i + 2
			j = j + 2
	if sorted(arr) == arr:
		return True
	else:
		return False
while True:
	try:
		test = int(input())
	except EOFError:
		break
	for i in range(test):
		a = int(input())
		arr = list(map(int, input().split(' ')))
		if ans(arr):
			print('YES')
		else:
			print('NO')


def helper():
	tstcs = int(input())
	for i in range(tstcs):
		l = int(input())
		arr = [int(x) for x in input().split()]
		if len(arr) % 2 == 0:
			indx = 1
			while indx < len(arr):
				if arr[indx] < arr[indx - 1]:
					(arr[indx], arr[indx - 1]) = (arr[indx - 1], arr[indx])
				indx += 2
		else:
			indx = 2
			while indx < len(arr):
				if arr[indx] < arr[indx - 1]:
					(arr[indx], arr[indx - 1]) = (arr[indx - 1], arr[indx])
				indx += 2
		flag = True
		indx_n = 1
		while indx_n < len(arr):
			if arr[indx_n] < arr[indx_n - 1]:
				flag = False
				break
			indx_n += 1
		if flag:
			print('YES')
		else:
			print('NO')
helper()


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split(' ')))
	temp2 = []
	i = len(arr) % 2
	while i < len(arr):
		if arr[i] > arr[i + 1]:
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		i += 2
	temp2 = arr.copy()
	arr.sort()
	if temp2 == arr:
		print('YES')
	else:
		print('NO')
	t -= 1


def check(n, l):
	if n == 1:
		return 'YES'
	if n % 2 == 0:
		start = 0
		past = -1
	else:
		start = 1
		past = l[0]
	for i in range(start, n, 2):
		if l[i] > l[i + 1]:
			(l[i], l[i + 1]) = (l[i + 1], l[i])
		if past > l[i]:
			return 'NO'
		else:
			past = l[i + 1]
	return 'YES'
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(check(n, l))


def work(a, b, c):
	d = True
	for j in range(0, a - 2, 2):
		if b[j] == c[j] and b[j + 1] == c[j + 1] or (b[j] == c[j + 1] and b[j + 1] == c[j]):
			d = True
		else:
			d = False
			break
	return d
for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	c = sorted(b)
	if a % 2 == 0:
		print('YES' if work(a, b, c) else 'NO')
	elif b[0] == c[0] and work(a - 1, b[1:], c[1:]):
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	a = int(input())
	lis = list(map(int, input().split()))
	x = lis.copy()
	x.sort()
	for i in range(a % 2, a, 2):
		if lis[i] > lis[i + 1]:
			(lis[i], lis[i + 1]) = (lis[i + 1], lis[i])
	if x == lis:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	flag = 1
	if n % 2:
		if nums[0] != min(nums):
			print('NO')
			continue
		nums.pop(0)
		n -= 1
	for i in range(0, n - 2, 2):
		if (nums[i] > nums[i + 2] or nums[i] > nums[i + 3]) or (nums[i + 1] > nums[i + 2] or nums[i + 1] > nums[i + 3]):
			flag = 0
			break
	if flag:
		print('YES')
	else:
		print('NO')


def check(n, arr):
	narr = arr.copy()
	narr.sort()
	for i in range(0, n, 2):
		(o1, o2) = (arr[i], arr[i + 1])
		(s1, s2) = (narr[i], narr[i + 1])
		if o1 == s1 and o2 == s2 or (o1 == s2 and o2 == s1):
			continue
		else:
			return False
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	flag = True
	if n % 2:
		if min(arr) != arr[0]:
			flag = False
		n -= 1
		arr = arr[1:]
	if flag and check(n, arr):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	flag = 0
	if not n % 2:
		for i in range(0, n, 2):
			if num[i] > num[i + 1]:
				(num[i], num[i + 1]) = (num[i + 1], num[i])
				if i + 2 < n and num[i + 1] > num[i + 2]:
					flag = 0
					break
				else:
					flag = 1
		if sorted(num) != num:
			flag = 0
		else:
			flag = 1
	else:
		for i in range(1, n - 1, 2):
			if num[i] > num[i + 1]:
				(num[i], num[i + 1]) = (num[i + 1], num[i])
				if i + 2 < n and num[i + 1] > num[i + 2]:
					flag = 0
					break
				else:
					flag = 1
		if sorted(num) != num:
			flag = 0
		else:
			flag = 1
	if flag:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n % 2 == 0:
		for i in range(0, n - 1, 2):
			if l[i] > l[i + 1]:
				a = l[i]
				l[i] = l[i + 1]
				l[i + 1] = a
	else:
		for i in range(1, n - 1, 2):
			if l[i] > l[i + 1]:
				a = l[i]
				l[i] = l[i + 1]
				l[i + 1] = a
	ch = True
	for i in range(n - 1):
		if l[i] > l[i + 1]:
			ch = False
			break
	if ch:
		print('YES')
	else:
		print('NO')


import math

def solve(a, n):
	c = []
	s = 0
	if n % 2 != 0:
		s = 1
		c.append(a[0])
	for i in range(s, n - 1, 2):
		if a[i] < a[i + 1]:
			c.append(a[i])
			c.append(a[i + 1])
		else:
			c.append(a[i + 1])
			c.append(a[i])
	for i in range(n - 1):
		if c[i] > c[i + 1]:
			return 'NO'
	return 'YES'
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(a, n))


for t in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	ans = sorted(li)
	if n % 2 and li[0] != min(li):
		print('NO')
	else:
		flag = 1
		if n % 2 == 0:
			start = 0
		else:
			start = 1
		for i in range(start, n - 1, 2):
			if (li[i], li[i + 1]) != (ans[i], ans[i + 1]) and (li[i + 1], li[i]) != (ans[i], ans[i + 1]):
				flag = 0
				break
		if flag:
			print('YES')
		else:
			print('NO')


t = int(input())
for _ in range(0, t):
	n = int(input())
	list1 = [int(num) for num in input().split()]
	flag = 0
	temp1 = [num for num in list1]
	if n % 2 == 0:
		for i in range(0, len(list1), 2):
			if list1[i] > list1[i + 1]:
				temp = list1[i]
				list1[i] = list1[i + 1]
				list1[i + 1] = temp
				if i + 2 < n and list1[i + 1] > list1[i + 2]:
					flag = 1
					break
		if list1 != sorted(temp1):
			flag = 1
	else:
		min1 = min(list1)
		if list1[0] != min1:
			flag = 1
		else:
			for i in range(1, len(list1), 2):
				if list1[i] > list1[i + 1]:
					temp = list1[i]
					list1[i] = list1[i + 1]
					list1[i + 1] = temp
				if i + 2 < n and list1[i + 1] > list1[i + 2]:
					flag = 1
					break
			if list1 != sorted(temp1):
				flag = 1
	if flag == 0:
		print('YES')
	else:
		print('NO')


kvs = int(input())
for _ in range(kvs):
	b = int(input())
	a = list(map(int, input().split()))
	for i in range(b % 2, b, 2):
		if a[i] > a[i + 1]:
			(a[i], a[i + 1]) = (a[i + 1], a[i])
	if sorted(a) == a:
		print('YES')
	else:
		print('NO')


t = int(input())
l = []
ln = []
for _ in range(t):
	ln += [int(input())]
	l += [list(map(int, input().split()))]
for i in range(t):
	lena = ln[i]
	a = l[i]
	f = 0
	if lena < 3:
		print('YES')
	elif lena % 2 == 1:
		if a[0] == min(a):
			a = a[1:]
			lena -= 1
			for k in range(0, lena, 2):
				if a[k] > a[k + 1]:
					(a[k], a[k + 1]) = (a[k + 1], a[k])
				if k != lena - 2:
					if a[k + 1] > min(a[k + 2], a[k + 3]):
						print('NO')
						f = 1
						break
		else:
			print('NO')
			f = 1
		if f == 0:
			print('YES')
	elif lena % 2 == 0:
		for k in range(0, lena, 2):
			if a[k] > a[k + 1]:
				(a[k], a[k + 1]) = (a[k + 1], a[k])
			if k != lena - 2:
				if a[k + 1] > min(a[k + 2], a[k + 3]):
					print('NO')
					f = 1
					break
		if f == 0:
			print('YES')


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	ans = True
	marker = 1000000000.0
	if n % 2 == 0:
		while a:
			first = a.pop()
			second = a.pop()
			if first > marker or second > marker:
				ans = False
				break
			else:
				marker = min(marker, first, second)
	else:
		while len(a) > 1:
			first = a.pop()
			second = a.pop()
			if first > marker or second > marker:
				ans = False
				break
			else:
				marker = min(marker, first, second)
		if a[0] > marker:
			ans = False
	if ans:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	f = 0
	for i in range(n % 2, n, 2):
		if l[i] > l[i + 1]:
			(l[i], l[i + 1]) = (l[i + 1], l[i])
	for i in range(1, n):
		if l[i] < l[i - 1]:
			print('NO')
			f = 1
			break
	if f == 0:
		print('YES')


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if len(a) == 1:
		print('YES')
	elif len(a) % 2 == 0:
		for i in range(0, len(a) - 2, 2):
			if max(a[i], a[i + 1]) <= min(a[i + 2], a[i + 3]):
				c = 0
			else:
				print('NO')
				break
		else:
			print('YES')
	elif a[0] <= min(a[1], a[2]):
		for i in range(1, len(a) - 3, 2):
			if max(a[i], a[i + 1]) <= min(a[i + 2], a[i + 3]):
				c = 0
			else:
				print('NO')
				break
		else:
			print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l1 = [int(a) for a in input().split()]
	l2 = sorted(l1)
	f = 0
	if n % 2:
		if l1[0] == l2[0]:
			l1 = l1[1:]
			n -= 1
			l2 = l2[1:]
		else:
			f = 1
	for i in range(n // 2):
		l3 = [l1[2 * i], l1[2 * i + 1]]
		l3.sort()
		if l3[0] == l2[2 * i] and l3[1] == l2[2 * i + 1]:
			pass
		else:
			f = 1
			break
	if f == 1:
		print('NO')
	else:
		print('YES')


def solve() -> bool:
	n = int(input())
	array = list(reversed(list(map(int, input().split()))))
	for index in range(0, n, 2):
		try:
			if array[index + 1] > array[index]:
				(array[index + 1], array[index]) = (array[index], array[index + 1])
		except IndexError:
			break
	for index in range(1, n):
		if array[index] > array[index - 1]:
			return False
	return True
for _ in range(int(input())):
	print('YES' if solve() else 'NO')


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


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ok = True
	for i in range(n - 3, -1, -2):
		m = max(a[i], a[i - 1]) if i > 0 else a[i]
		if m > min(a[i + 1], a[i + 2]):
			ok = False
	print('YES' if ok else 'NO')


def solve():
	N = int(input())
	arr = list(map(int, input().split()))
	arr1 = []
	for i in range(N):
		arr1.append(arr[i])
	arr1.sort()
	if N % 2 == 0:
		j = 0
		while j < N - 1:
			if arr1[j] == arr[j] and arr1[j + 1] == arr[j + 1] or (arr1[j] == arr[j + 1] and arr1[j + 1] == arr[j]):
				j += 2
			else:
				return 'NO'
		return 'YES'
	else:
		if arr1[0] != arr[0]:
			return 'NO'
		j = 1
		while j < N - 1:
			if arr1[j] == arr[j] and arr1[j + 1] == arr[j + 1] or (arr1[j] == arr[j + 1] and arr1[j + 1] == arr[j]):
				j += 2
			else:
				return 'NO'
		return 'YES'
remianed_test_cases = 1
remianed_test_cases = int(input())
while remianed_test_cases > 0:
	print(solve())
	remianed_test_cases -= 1


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	if n % 2 == 0:
		start = 0
	else:
		start = 1
	for i in range(start, n - 1, 2):
		if A[i] > A[i + 1]:
			(A[i], A[i + 1]) = (A[i + 1], A[i])
	flag = 0
	for i in range(1, n):
		if A[i] < A[i - 1]:
			flag = 1
			break
	if flag:
		print('NO')
	else:
		print('YES')
t = int(input())
while t != 0:
	solve()
	t -= 1


import math

def ans():
	n = int(input())
	a = list(map(int, input().split()))
	biggest = 0
	start = 0
	if n % 2 == 0:
		biggest = max(a[0], a[1])
		start = 2
	else:
		biggest = a[0]
		start = 1
	for i in range(start, n, 2):
		(small, big) = (min(a[i], a[i + 1]), max(a[i], a[i + 1]))
		if small >= biggest:
			biggest = big
			continue
		else:
			return 'NO'
	return 'YES'
for i in range(int(input())):
	print(ans())


def solve(n, a):
	if n == 1:
		return 'YES'
	aUnsort = a.copy()
	a.sort()
	for i in range(n):
		if n % 2 == 0:
			if i % 2 == 0:
				if aUnsort[i] != a[i] and aUnsort[i] != a[i + 1]:
					return 'NO'
			elif aUnsort[i] != a[i] and aUnsort[i] != a[i - 1]:
				return 'NO'
		else:
			if i == 0 and a[0] != aUnsort[0]:
				return 'NO'
			if i % 2 == 1:
				if aUnsort[i] != a[i] and aUnsort[i] != a[i + 1]:
					return 'NO'
			elif aUnsort[i] != a[i] and aUnsort[i] != a[i - 1]:
				return 'NO'
	return 'YES'
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	print(solve(n, a))


for _ in [0] * int(input()):
	n = int(input())
	a = [*map(int, input().split())]
	for i in range(n % 2, n, 2):
		if a[i] > a[i + 1]:
			(a[i], a[i + 1]) = (a[i + 1], a[i])
	ans = 'YES'
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			ans = 'NO'
			break
	print(ans)