You are given an array $a_1, a_2, \dots, a_n$. You can perform operations on the array. In each operation you can choose an integer $i$ ($1 \le i < n$), and swap elements $a_i$ and $a_{i+1}$ of the array, if $a_i + a_{i+1}$ is odd.

Determine whether it can be sorted in non-decreasing order using this operation any number of times.


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Description of the test cases follows.

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

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

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print "Yes" or "No" depending on whether you can or can not sort the given array.

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).


-----Examples-----

Input
4
4
1 6 31 14
2
4 2
5
2 9 6 7 10
3
6 6 6
Output
Yes
No
No
Yes


-----Note-----

In the first test case, we can simply swap $31$ and $14$ ($31 + 14 = 45$ which is odd) and obtain the non-decreasing array $[1,6,14,31]$.

In the second test case, the only way we could sort the array is by swapping $4$ and $2$, but this is impossible, since their sum $4 + 2 = 6$ is even.

In the third test case, there is no way to make the array non-decreasing.

In the fourth test case, the array is already non-decreasing.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Data structures

Mathematics


Solutions:
import sys

def solution(array):
	max_even = 0
	max_odd = 0
	for a in array:
		if a % 2 == 0:
			if a < max_even:
				print('No')
				return
			else:
				max_even = a
		elif a < max_odd:
			print('No')
			return
		else:
			max_odd = a
	print('Yes')
	return
input = sys.stdin.read().splitlines()
t = int(input[0])
offset = 1
for test in range(t):
	n = input[2 * test + offset]
	array = input[2 * test + offset + 1].split(' ')
	array = [int(e) for e in array]
	solution(array)


import sys
T = int(sys.stdin.readline())
for t in range(T):
	n = int(sys.stdin.readline())
	a = [int(x) for x in sys.stdin.readline().split(' ')]
	odd = -1
	even = 0
	flag = True
	for x in a:
		if x % 2 == 1:
			if odd > x:
				flag = False
				break
			odd = x
		else:
			if even > x:
				flag = False
				break
			even = x
	if flag:
		print('Yes')
	else:
		print('No')


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	b = [[], []]
	for i in a:
		b[i % 2].append(i)
	for i in b:
		if i != sorted(i):
			print('No')
			return
	print('Yes')

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


import sys
from typing import List

def sol(perm: List[int]) -> bool:
	biggest_odd = 0
	biggest_even = 0
	for number in perm:
		if number % 2 == 0:
			if biggest_even > number:
				return False
			biggest_even = max(number, biggest_even)
		else:
			if biggest_odd > number:
				return False
			biggest_odd = max(number, biggest_odd)
	return True

def main():
	inp = sys.stdin.readlines()
	rest = inp[1:]
	permutations = rest[1::2]
	permutations = [[int(num) for num in line.split()] for line in permutations]
	for perm in permutations:
		if sol(perm):
			print('Yes')
		else:
			print('No')
main()


for s in [*open(0)][2::2]:
	a = [[], []]
	for x in map(int, s.split()):
		a[x & 1] += (x,)
	print('YNeos'[any((x > sorted(x) for x in a))::2])


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(o, e) = ([], [])
	for i in arr:
		if i % 2 != 0:
			o.append(i)
		else:
			e.append(i)
	(te, to) = (e[:], o[:])
	te.sort()
	to.sort()
	if te == e and to == o:
		print('Yes')
	else:
		print('No')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	a = []
	b = []
	for i in range(n):
		if A[i] % 2 == 0:
			a.append(A[i])
		else:
			b.append(A[i])
	if a == sorted(a) and b == sorted(b):
		print('Yes')
	else:
		print('No')


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	odd = -1
	even = -1
	ans = True
	for i in range(n):
		if a[i] % 2 == 0:
			if a[i] < even:
				ans = False
				break
			else:
				even = a[i]
		elif a[i] < odd:
			ans = False
			break
		else:
			odd = a[i]
	if not ans:
		print('No')
	else:
		print('Yes')


import sys
input = sys.stdin.readline

def solve(n, arr):
	maxEven = -float('inf') if arr[0] % 2 == 1 else arr[0]
	maxOdd = -float('inf') if arr[0] % 2 == 0 else arr[0]
	prev = arr[0]
	for curr in arr:
		if curr % 2 == 0:
			if maxEven > curr:
				print('No')
				return
			maxEven = max(maxEven, curr)
		else:
			if maxOdd > curr:
				print('No')
				return
			maxOdd = max(maxOdd, curr)
	print('Yes')
	return
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	solve(n, arr)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	odd = []
	even = []
	for i in a:
		if i & 1:
			odd.append(i)
		else:
			even.append(i)
	if odd == sorted(odd) and even == sorted(even):
		print('Yes')
	else:
		print('No')


for s in [*open(0)][2::2]:
	a = list(map(int, s.split()))
	cls = [[], []]
	for n in a:
		cls[n & 1] += (n,)
	print('No' if any((c > sorted(c) for c in cls)) else 'Yes')


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	o = []
	e = []
	for j in range(n):
		if a[j] % 2 == 0:
			e.append(a[j])
		else:
			o.append(a[j])
	if e == sorted(e) and o == sorted(o):
		res = 'Yes'
	else:
		res = 'No'
	print(res)


for s in [*open(0)][2::2]:
	a = [*map(int, s.split())]
	last_ev = len(a) - 1
	ods = []
	evs = []
	for (i, v) in enumerate(a):
		if v % 2:
			ods.append(v)
			last_ev = i
		else:
			evs.append(v)
	not_pos = False
	for i in range(1, len(evs)):
		if evs[i] >= evs[i - 1]:
			continue
		else:
			not_pos = True
	for i in range(1, len(ods)):
		if ods[i] >= ods[i - 1]:
			continue
		else:
			not_pos = True
	if not_pos:
		print('No')
		continue
	else:
		print('Yes')


import sys
input = sys.stdin.readline
sI = lambda : input()
iI = lambda : int(input())
mI = lambda : map(int, input().split())
lI = lambda : list(mI())
for _ in range(iI()):
	n = iI()
	a = lI()
	odd = [i for i in a if i % 2]
	ev = [i for i in a if i % 2 == 0]
	if odd == sorted(odd) and ev == sorted(ev):
		print('Yes')
	else:
		print('No')


import sys
input = sys.stdin.readline

def sorted(iter):
	return all((iter[i] <= iter[i + 1] for i in range(len(iter) - 1)))
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	even = []
	odd = []
	for num in a:
		if num % 2 == 0:
			even.append(num)
		else:
			odd.append(num)
	if sorted(even) and sorted(odd):
		print('Yes')
	else:
		print('No')


cases = int(input())
ans = []
for _ in range(cases):
	num = int(input())
	arr = list(map(int, input().split()))
	odds = [n for n in arr if n % 2]
	evens = [n for n in arr if n % 2 == 0]
	if sorted(odds) == odds and sorted(evens) == evens:
		ans.append('Yes')
	else:
		ans.append('No')
for a in ans:
	print(a)


N = int(input())
inputs = []
for i in range(N):
	num = int(input())
	arr = list(map(int, input().split()))
	inputs.append(arr)
ans = []
for arr in inputs:
	left = right = -1
	check = True
	for i in range(len(arr)):
		if arr[i] % 2 == 1:
			if arr[i] < right:
				check = False
				break
			right = arr[i]
			continue
		if arr[i] < left:
			check = False
			break
		left = arr[i]
	if check:
		ans.append('Yes')
	else:
		ans.append('No')
for elm in ans:
	print(elm)


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq
from unittest import TestCase

def input():
	return sys.stdin.readline()[:-1]
INF = 10 ** 10
YES = 'Yes'
NO = 'No'

def solve(N, A):
	v = 0
	for a in A:
		if a % 2 == 0:
			if v > a:
				return 'No'
			v = a
	v = 0
	for a in A:
		if a % 2 == 1:
			if v > a:
				return 'No'
			v = a
	return 'Yes'
T0 = int(input())
for _ in range(T0):
	N = int(input())
	A = list(map(int, input().split()))
	print(solve(N, A))


t = int(input())
results = []
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	a = [x for x in arr if x % 2 == 0]
	b = [x for x in arr if x % 2 == 1]
	flag = True
	for i in range(len(a) - 1):
		if a[i] > a[i + 1]:
			flag = False
			break
	for i in range(len(b) - 1):
		if b[i] > b[i + 1]:
			flag = False
			break
	results.append('Yes' if flag else 'No')
for r in results:
	print(r)


t = int(input())
ans = ['Yes'] * t
for q in range(t):
	chet = []
	nech = []
	n = int(input())
	arr = [*map(int, input().split())]
	for i in range(len(arr)):
		if arr[i] % 2 == 0:
			chet.append(arr[i])
		if arr[i] % 2 == 1:
			nech.append(arr[i])
	if len(nech) > 0:
		for y in range(len(nech) - 1):
			if nech[y] > nech[y + 1]:
				ans[q] = 'No'
				break
	if len(chet) > 0:
		for x in range(len(chet) - 1):
			if chet[x] > chet[x + 1]:
				ans[q] = 'No'
				break
for r in range(t):
	print(ans[r])


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		a = int(input())
		print('Yes')
	else:
		a = list(map(int, input().split()))
		a_even = []
		a_odd = []
		for i in range(n):
			if a[i] % 2 == 0:
				a_even.append(a[i])
			else:
				a_odd.append(a[i])
		a.sort()
		i_even = 0
		i_odd = 0
		for i in range(n):
			if a[i] % 2 == 0 and a[i] == a_even[i_even]:
				i_even += 1
			elif a[i] % 2 == 1 and a[i] == a_odd[i_odd]:
				i_odd += 1
			else:
				print('No')
				break
		else:
			print('Yes')


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	shu = [0, 0]
	k = 0
	if arr == sorted(arr):
		print('Yes')
	else:
		for i in range(n):
			if arr[i] % 2 == 1:
				if arr[i] >= shu[1]:
					shu[1] = arr[i]
				else:
					print('No')
					break
			elif arr[i] >= shu[0]:
				shu[0] = arr[i]
			else:
				print('No')
				break
		else:
			print('Yes')


def solve(l):
	if len(l) == 1:
		return True
	pairs = -1
	impairs = -1
	for elem in l:
		if elem % 2 == 0:
			if elem < pairs:
				return False
			else:
				pairs = elem
		elif elem < impairs:
			return False
		else:
			impairs = elem
	return True
for _ in range(int(input())):
	x = int(input())
	l = [int(i) for i in input().split()]
	if solve(l):
		print('Yes')
	else:
		print('No')


import sys

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

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

def main():
	for _ in range(int(input())):
		n = int(input())
		ls = get_ls()
		odd = []
		even = []
		for x in ls:
			if x % 2 == 0:
				even.append(x)
			else:
				odd.append(x)
		t1 = odd.copy()
		t2 = even.copy()
		t1.sort()
		t2.sort()
		if t1 == odd and t2 == even:
			print('Yes')
		else:
			print('No')
main()


def solveB(a):
	if len(a) == 1:
		return 'Yes'
	prevOdd = float('-inf')
	prevEven = float('-inf')
	for value in a:
		if value % 2 == 0 and prevEven <= value:
			prevEven = value
		elif value % 2 == 1 and prevOdd <= value:
			prevOdd = value
		else:
			return 'No'
	return 'Yes'
num_tests = int(input().split()[0])
for t in range(num_tests):
	n = int(input().split()[0])
	a = [int(x) for x in input().split()]
	print(solveB(a))