One day Prof. Slim decided to leave the kingdom of the GUC to join the kingdom of the GIU. He was given an easy online assessment to solve before joining the GIU. Citizens of the GUC were happy sad to see the prof leaving, so they decided to hack into the system and change the online assessment into a harder one so that he stays at the GUC. After a long argument, they decided to change it into the following problem.

Given an array of $n$ integers $a_1,a_2,\ldots,a_n$, where $a_{i} \neq 0$, check if you can make this array sorted by using the following operation any number of times (possibly zero). An array is sorted if its elements are arranged in a non-decreasing order.

select two indices $i$ and $j$ ($1 \le i,j \le n$) such that $a_i$ and $a_j$ have different signs. In other words, one must be positive and one must be negative.

swap the signs of $a_{i}$ and $a_{j}$. For example if you select $a_i=3$ and $a_j=-2$, then they will change to $a_i=-3$ and $a_j=2$.

Prof. Slim saw that the problem is still too easy and isn't worth his time, so he decided to give it to you to solve.


-----Input-----

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

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

The next line contain $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_{i} \le 10^9$, $a_{i} \neq 0$) separated by spaces describing elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$.


-----Output-----

For each test case, print "YES" if the array can be sorted in the non-decreasing order, otherwise print "NO". You can print each letter in any case (upper or lower).


-----Examples-----

Input
4
7
7 3 2 -11 -13 -17 -23
6
4 10 25 47 71 96
6
71 -35 7 -4 -11 -25
6
-45 9 -48 -67 -55 7
Output
NO
YES
YES
NO


-----Note-----

In the first test case, there is no way to make the array sorted using the operation any number of times.

In the second test case, the array is already sorted.

In the third test case, we can swap the sign of the $1$-st element with the sign of the $5$-th element, and the sign of the $3$-rd element with the sign of the $6$-th element, this way the array will be sorted.

In the fourth test case, there is no way to make the array sorted using the operation any number of times.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Implementation

Greedy algorithms


Solutions:
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	w = input()[:-1]
	c = w.count('-')
	w = list(map(int, w.replace('-', '').split()))
	i = 0
	while c:
		w[i] = -w[i]
		c -= 1
		i += 1
	if w == sorted(w):
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = 0
	for i in range(n):
		if arr[i] < 0:
			cnt += 1
	prev = abs(arr[0])
	for i in range(n):
		if i < cnt:
			if prev < abs(arr[i]):
				return 'NO'
			prev = abs(arr[i])
		elif i == cnt:
			prev = abs(arr[i])
		else:
			if prev > abs(arr[i]):
				return 'NO'
			prev = abs(arr[i])
	return 'YES'
for _ in range(int(input())):
	print(solve())


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	flag = False
	(left, right) = (0, n - 1)
	while left < right:
		if arr[left] > 0:
			while arr[right] > 0 and left < right:
				right -= 1
			if left < right:
				arr[left] *= -1
				arr[right] *= -1
			else:
				break
		left += 1
	for i in range(n - 1):
		if arr[i] > arr[i + 1]:
			print('NO')
			break
	else:
		print('YES')


from sys import stdin, stdout
import collections
import math

def solve():
	return

def main():
	for i in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		g = []
		ans = True
		c = 0
		for i in range(n):
			if l[i] < 0:
				l[i] = -l[i]
				c += 1
		for i in range(n):
			if c == 0:
				break
			if l[i] > 0:
				l[i] = -l[i]
				c -= 1
		if l != sorted(l):
			ans = False
		if ans:
			print('YES')
		else:
			print('NO')
	return
input = stdin.readline
main()


import copy
n = int(input())
datas = []
for i in range(n):
	t = int(input())
	data = list(map(int, input().split()))
	datas.append(data)

def is_sorted(data):
	if not data:
		return True
	c = data[0]
	for d in data[1:]:
		if d < c:
			return False
		c = d
	return True

def check(data):
	if is_sorted(data):
		return True
	neg_count = 0
	pos_count = 0
	for d in data:
		if d < 0:
			neg_count += 1
		if d > 0:
			pos_count += 1
	for i in range(neg_count):
		if data[i] > 0:
			data[i] = data[i] * -1
	for i in range(pos_count):
		index = (i + 1) * -1
		if data[index] < 0:
			data[index] = data[index] * -1
	return is_sorted(data)
for data in datas:
	if check(data):
		print('YES')
	else:
		print('NO')


import sys

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

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

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

def SI():
	return sys.stdin.readline().strip()
for _ in range(II()):
	n = II()
	arr = LI()
	absArr = []
	negNumbers = 0
	for i in arr:
		if i < 0:
			negNumbers += 1
	isBig = 0
	for i in arr:
		if negNumbers > 0:
			absArr.append(-abs(i))
			negNumbers -= 1
		else:
			absArr.append(abs(i))
	print('YES' if absArr == sorted(absArr) else 'NO')


from operator import ne

def main():

	def solve(n, a):
		neg = 0
		for i in range(n):
			if a[i] < 0:
				neg += 1
				a[i] = -a[i]
		for i in range(neg):
			a[i] = -a[i]
		for i in range(1, n):
			if a[i] < a[i - 1]:
				return 'NO'
		return 'YES'
	t = int(input())
	ans = []
	for _ in range(t):
		n = int(input())
		a = [int(x) for x in input().split()]
		ans.append(solve(n, a))
	print('\n'.join(ans))
import sys, threading
input = sys.stdin.readline
thread = threading.Thread(target=main)
thread.start()
thread.join()


import sys
input = sys.stdin.readline
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	ct = 0
	for i in range(n):
		if a[i] < 0:
			ct += 1
	flag = 0
	for i in range(1, ct):
		if abs(a[i]) <= abs(a[i - 1]):
			pass
		else:
			flag = 1
	if flag == 0:
		for i in range(ct, n - 1):
			if abs(a[i + 1]) >= abs(a[i]):
				pass
			else:
				flag = 1
	if flag == 1:
		print('NO')
	else:
		print('YES')


from math import inf, gcd, log, log2, floor, ceil, sqrt
from collections import Counter, defaultdict
from heapq import heappush, heappop, heapify
from functools import lru_cache
import sys
DIRS = [[1, 0], [0, 1], [0, -1], [-1, 0], [-1, -1], [1, 1], [-1, 1], [1, -1]]
MOD = 10 ** 9 + 7
input = sys.stdin.readline
t = int(input())

def solve():
	n = int(input())
	A = [int(x) for x in input().split(' ')]
	cnt = sum([x < 0 for x in A])
	for i in range(1, cnt):
		if abs(A[i]) > abs(A[i - 1]):
			return False
	for i in range(cnt + 1, n):
		if abs(A[i]) < abs(A[i - 1]):
			return False
	return True
while t:
	out = solve()
	if out:
		print('YES')
	else:
		print('NO')
	t -= 1


import sys
ls = []
for l in sys.stdin:
	lst = l.rstrip('\n')
	if len(lst) > 0:
		ls.append(lst)
for l in ls:
	sys.stderr.write(l + '\n')
sys.stderr.write('-- output --\n')

def solve(n, a):
	k = sum([0 if ai > 0 else 1 for ai in a])
	b = [abs(a[i]) if i >= k else -abs(a[i]) for i in range(n)]
	for i in range(n - 1):
		if b[i] > b[i + 1]:
			return 'NO'
	return 'YES'
for i in range(1, len(ls) - 1, 2):
	n = int(ls[i])
	a = [int(x) for x in ls[i + 1].split(' ')]
	print(solve(n, a))


import math, bisect, heapq, random, sys, itertools
sys.setrecursionlimit(2 * 10 ** 5)
input = sys.stdin.readline

def gprint(t, ans=''):
	print(f'Case #{t + 1}:', ans)
ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p2 = [1]
p = 10 ** 9 + 7
inf = 10 ** 20 + 7
fact = [1]
ANS = []
for t in range(int(input())):
	n = int(input())
	a = ints()
	c = 0
	for i in a:
		if i < 0:
			c += 1
	for i in range(n):
		if i < c:
			a[i] = -1 * abs(a[i])
		else:
			a[i] = abs(a[i])
	if a == sorted(a):
		print('YES')
	else:
		print('NO')


import sys
inp = sys.stdin.readline
for _ in range(int(inp())):
	n = int(inp())
	l = list(map(int, inp().split()))
	c = 0
	y = 0
	v = 0
	b = True
	for i in range(n):
		if l[i] < 0:
			y = y + 1
	for i in range(y):
		l[i] = abs(l[i]) * -1
	for i in range(y, n):
		l[i] = abs(l[i])
	if l == sorted(l):
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline

def is_sorted(A):
	for (a, b) in zip(A, A[1:]):
		if a > b:
			return False
	return True
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	n_neg = sum((a < 0 for a in A))
	B = [-abs(a) if i < n_neg else abs(a) for (i, a) in enumerate(A)]
	print('YES' if is_sorted(B) else 'NO')


def main():
	for _ in range(int(input())):
		(_, s) = (input(), input())
		cnt = s.count('-')
		l = list(map(int, s.replace('-', '').split()))
		(a, b) = (l[:cnt], l[cnt:])
		l[:cnt] = l[:cnt][::-1]
		print(('NO', 'YES')[a == sorted(a, reverse=True) and b == sorted(b)])
main()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for i in a:
		if i < 0:
			count += 1
	cur = -10 ** 10
	ans = True
	for k in a:
		if count > 0:
			if -abs(k) < cur:
				ans = False
				break
			else:
				cur = -abs(k)
		elif abs(k) < cur:
			ans = False
			break
		else:
			cur = abs(k)
		count -= 1
	if ans:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	num_neg = 0
	for i in map(int, input().split()):
		if i < 0:
			num_neg += 1
			a.append(-i)
		else:
			a.append(i)
	ans = 'YES'
	for i in range(1, num_neg):
		if a[i - 1] < a[i]:
			ans = 'NO'
	for i in range(num_neg + 1, n):
		if a[i - 1] > a[i]:
			ans = 'NO'
	print(ans)


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


def is_sortable(a):
	if len(a) == 1:
		return True
	idx_first = 0
	idx_last = len(a) - 1
	while idx_first < idx_last:
		while idx_first < idx_last and a[idx_first] < 0:
			idx_first += 1
		while idx_first < idx_last and a[idx_last] > 0:
			idx_last -= 1
		if idx_first < idx_last and a[idx_first] > 0 and (a[idx_last] < 0):
			a[idx_first] *= -1
			a[idx_last] *= -1
	for i in range(len(a) - 1):
		if a[i] > a[i + 1]:
			return False
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(number) for number in input().split()]
	print('YES' if is_sortable(a) else 'NO')


for _ in range(int(input())):
	n = int(input())
	arr = [int(a) for a in input().split()]
	(i, j) = (0, n - 1)
	while i < j:
		while i < j and arr[i] < 0:
			i += 1
		while i < j and arr[j] > 0:
			j -= 1
		if i < j:
			arr[i] *= -1
			arr[j] *= -1
			i += 1
			j -= 1
	print('YES' if sorted(arr) == arr else 'NO')


from collections import deque

def checker():
	q = deque()
	n = int(input())
	nums = list(map(int, input().split()))
	for i in range(n):
		if nums[i] < 0:
			if q:
				index = q.popleft()
				nums[index] *= -1
				nums[i] *= -1
				q.append(i)
		elif nums[i] > 0:
			q.append(i)
	if nums == sorted(nums):
		return 'YES'
	else:
		return 'NO'
test = int(input())
for i in range(test):
	x = checker()
	print(x)


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	for i in range(len(arr)):
		if arr[i] < 0:
			count += 1
	for i in range(len(arr)):
		if count:
			count -= 1
			arr[i] = -abs(arr[i])
		else:
			arr[i] = abs(arr[i])
	if arr == sorted(arr):
		return 'YES'
	else:
		return 'NO'
t = int(input())
for _ in range(t):
	print(solve())


for i in range(int(input())):
	t = int(input())
	a = list(map(int, input().split()))
	b = 0
	for i in range(t):
		if a[i] < 0:
			b += 1
			a[i] = -a[i]
		else:
			pass
	for i in range(b):
		a[i] = -a[i]
	if sorted(a) == a:
		print('YES')
	else:
		print('NO')


def solve():
	for tc in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		neg = 0
		for i in range(n):
			if arr[i] < 0:
				arr[i] -= 2 * arr[i]
				neg += 1
		for i in range(neg):
			arr[i] = -arr[i]
		if sorted(arr) == arr:
			print('YES')
		else:
			print('NO')
solve()


t = int(input())

def isSorted(n, arr):
	k = 0
	for a in range(n):
		if arr[a] < 0:
			k += 1
	for i in range(n):
		if i < k:
			if not arr[i] < 0:
				arr[i] = -arr[i]
		elif i >= k:
			if arr[i] < 0:
				arr[i] = -arr[i]
	for i in range(n):
		if i < k and i + 1 < k and (arr[i] > arr[i + 1]):
			return 'NO'
		elif i >= k and i + 1 < n and (arr[i] > arr[i + 1]):
			return 'NO'
	return 'YES'
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	print(isSorted(n, arr))


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	count = 0
	for i in range(n):
		if lis[i] < 0:
			lis[i] = -1 * lis[i]
			count += 1
	for j in range(count):
		lis[j] = -1 * lis[j]
	if lis == sorted(lis):
		print('YES')
	else:
		print('NO')


def solve():
	(N, A) = (int(input()), list(map(int, input().split())))
	X = 0
	for i in range(N):
		if A[i] < 0:
			X += 1
		A[i] = abs(A[i])
	for i in range(1, X):
		if A[i] > A[i - 1]:
			print('NO')
			return
	for i in range(X, N - 1):
		if A[i] > A[i + 1]:
			print('NO')
			return
	print('YES')
for _ in range(int(input())):
	solve()


n = int(input())
for _ in range(n):
	_ = input()
	numbers = [int(number) for number in input().split()]
	negative = 0
	for number in numbers:
		if number < 0:
			negative += 1
	is_non_decreasing = True
	previous_number = -float('inf')
	for number in numbers:
		if negative >= 1:
			number = -abs(number)
			negative = negative - 1
		else:
			number = abs(number)
		if previous_number > number:
			is_non_decreasing = False
			break
		previous_number = number
	if is_non_decreasing:
		print('YES')
	else:
		print('NO')


t = int(input())

def solution(n, a):
	cnt_neg = 0
	for elem in a:
		if elem < 0:
			cnt_neg += 1
	for i in range(1, n):
		if i < cnt_neg and abs(a[i]) > abs(a[i - 1]):
			return 'NO'
		elif i > cnt_neg and abs(a[i]) < abs(a[i - 1]):
			return 'NO'
	return 'YES'
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(solution(n, a))


for _ in range(int(input())):
	(n, a) = (int(input()), [*map(int, input().split())])
	no_of_neg_numbers = sum((1 if i < 0 else 0 for i in a))
	t = [abs(a[i]) * (-1 if i < no_of_neg_numbers else 1) for i in range(len(a))]
	if sorted(t) == t:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = 0
	for j in range(n):
		if a[j] < 0:
			b += 1
	c = []
	for j in range(b):
		c.append(abs(a[j]) * -1)
	for j in range(b, n):
		c.append(abs(a[j]))
	if c == sorted(c):
		print('YES')
	else:
		print('NO')


def main():
	for _ in range(int(input())):
		(_, s) = (input(), input())
		cnt = s.count('-')
		l = list(map(int, s.replace('-', '').split()))
		for i in range(cnt):
			l[i] *= -1
		print(('NO', 'YES')[l == sorted(l)])
main()


for j in range(0, int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	x = []
	for i in l:
		if i < 0:
			c = c + 1
	x = [abs(z) for z in l]
	for q in range(0, c):
		x[q] = x[q] * -1
	if x == sorted(x):
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	cc = 0
	for i in range(n):
		if a[i] < 0:
			cc += 1
	a = [abs(i) for i in a]
	for i in range(cc):
		a[i] = -a[i]
	if a == sorted(a):
		print('YES')
	else:
		print('NO')


t = int(input(''))
for _ in range(t):
	n = int(input(''))
	arr = list(map(int, input('').split(' ')))
	i = 0
	j = n - 1
	while i < j:
		if arr[j] < 0:
			if arr[i] > 0:
				arr[i] = -arr[i]
				arr[j] = abs(arr[j])
				i += 1
				j -= 1
			else:
				i += 1
		else:
			j -= 1
	a = sorted(arr)
	if arr == a:
		print('YES')
	else:
		print('NO')


for f in range(int(input())):
	(n, a) = (int(input()), [*map(int, input().split())])
	h = sum((1 for v in a if v < 0))
	b = [abs(a[i]) * (-1 if i < h else 1) for i in range(n)]
	print('YES' if sorted(b) == b else 'NO')


for _ in range(int(input())):
	(n, a) = (int(input()), list(map(int, input().split())))
	(p1, p2) = (0, n - 1)
	while True:
		while a[p1] < 0 and p1 < p2:
			p1 += 1
		while a[p2] > 0 and p1 < p2:
			p2 -= 1
		if p1 == p2:
			break
		(a[p1], a[p2]) = (-a[p1], -a[p2])
	print('YES' if sorted(a) == a else 'NO')


num_of_case = int(input())
for _ in range(num_of_case):
	N = int(input())
	arr = [int(x) for x in input().split(' ')]
	left = 0
	right = N - 1
	while left < right:
		while left < right and arr[left] < 0:
			left += 1
		while left < right and arr[right] >= 0:
			right -= 1
		if left < right:
			(arr[left], arr[right]) = (-arr[left], -arr[right])
			left += 1
			right -= 1
	result_printed = False
	for idx in range(1, N):
		if arr[idx] < arr[idx - 1]:
			print('NO')
			result_printed = True
			break
	if not result_printed:
		print('YES')


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


def solve(a, n):
	count = 0
	for x in a:
		if x < 0:
			count += 1
	for y in range(count - 1):
		if abs(a[y]) < abs(a[y + 1]):
			return 'NO'
	for z in range(count, n - 1):
		if abs(a[z]) > abs(a[z + 1]):
			return 'NO'
	return 'YES'
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = solve(a, n)
	print(b)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	neg = 0
	for i in range(n):
		if lst[i] < 0:
			neg += 1
			lst[i] = -lst[i]
	for i in range(neg):
		lst[i] = -lst[i]
	print('YES' if sorted(lst) == lst else 'NO')


def ver(n, a):
	m = 0
	k = 0
	for i in range(n):
		if a[i] < 0:
			k += 1
			a[i] = abs(a[i])
	for i in range(k):
		a[i] = -1 * a[i]
	if a == sorted(a):
		return 'YES'
	else:
		return 'NO'
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(ver(n, a))


import sys
import math
from math import gcd, sqrt, log2, ceil, floor
import heapq as hq
from bisect import bisect_right, bisect_left, bisect
import itertools
from sys import stdin, stdout, setrecursionlimit
MOD = int(1000000000.0) + 7
alp = 'abcdefghijklmnopqrstuvwxyz'
T = 1
T = int(stdin.readline())
for _ in range(T):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().rstrip().split()))
	nc = 0
	for i in range(n):
		if a[i] < 0:
			nc += 1
	for i in range(n):
		if i < nc:
			a[i] = -abs(a[i])
		else:
			a[i] = abs(a[i])
	A = a.copy()
	A.sort()
	if A == a:
		print('YES')
	else:
		print('NO')


import datetime
t = int(input())

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	k = 0
	for i in a:
		if i < 0:
			k += 1
	for i in range(1, n):
		if i < k:
			if abs(a[i]) > abs(a[i - 1]):
				print('NO')
				return
		elif i > k:
			if abs(a[i]) < abs(a[i - 1]):
				print('NO')
				return
	print('YES')
for i in range(t):
	solve()


def solve() -> bool:
	n = int(input())
	arr = list(map(int, input().split()))
	negative = 0
	for e in arr:
		if e < 0:
			negative += 1
	positive = n - negative
	for i in range(1, negative):
		if abs(arr[i - 1]) < abs(arr[i]):
			return False
	for i in range(negative + 1, n):
		if abs(arr[i - 1]) > abs(arr[i]):
			return False
	return True
for _ in range(int(input())):
	print('YES' if solve() else 'NO')


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()))
	j = 0
	for i in range(n):
		if A[i] < 0:
			A[i] = -1 * A[i]
			A[j] = -1 * A[j]
			j += 1
	if A == sorted(A):
		print('YES')
	else:
		print('NO')
t = int(input())
while t != 0:
	solve()
	t -= 1


import math
from collections import Counter

def fun(a):
	neg = 0
	for i in range(len(a)):
		if a[i] < 0:
			neg += 1
			a[i] *= -1
	for i in range(len(a)):
		if neg:
			a[i] *= -1
			neg -= 1
		else:
			break
	if a == sorted(a):
		return 1
n = int(input())
for _ in range(n):
	l = input()
	a = input().split()
	a = list(map(int, a))
	if fun(a):
		print('YES')
	else:
		print('NO')


for num in range(int(input())):
	an = int(input())
	al = list(map(int, input().split()))
	count = 0
	for i in al:
		if i < 0:
			count += 1
	if count == len(al) or count == 0:
		pass
	else:
		for j in range(count):
			if al[j] > 0:
				al[j] = al[j] * -1
		for k in range(count, len(al)):
			if al[k] < 0:
				al[k] = al[k] * -1
	sl = sorted(al)
	if al == sl:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, a) = (int(input()), [*map(int, input().split())])
	neg = sum((1 for v in a if v < 0))
	b = [abs(a[i]) * (-1 if i < neg else 1) for i in range(n)]
	print('YES' if sorted(b) == b else 'NO')


xx = int(input())

def cal(n, arr):
	x = 0
	for i in range(n):
		if arr[i] < 0:
			x += 1
			arr[i] = -arr[i]
	for i in range(x):
		arr[i] = -arr[i]
	if sorted(arr) == arr:
		return True
	return False
for jj in range(xx):
	n = int(input())
	arr = [int(i) for i in input().split(' ')]
	if cal(n, arr):
		print('YES')
	else:
		print('NO')


from sys import stdin
input = stdin.readline
rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip()
YN = lambda x: print('YES') if x else print('NO')
ceil_div = lambda a, b: -(-a // b)
mod = 10 ** 9 + 7
for _ in range(rn()):
	n = rn()
	a = rl()
	neg = len([i for i in range(n) if a[i] < 0])
	a = [abs(a[i]) for i in range(n)]
	for i in range(n):
		if a[i] > 0 and neg > 0:
			a[i] *= -1
			neg -= 1
	ans = True
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			ans = False
			break
	YN(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	i = 0
	j = len(arr) - 1
	while i < j:
		if arr[i] > 0 and arr[j] < 0:
			arr[i] *= -1
			arr[j] *= -1
			i += 1
			j -= 1
		elif arr[i] < 0:
			i += 1
		else:
			j -= 1
	if sorted(arr) == arr:
		print('YES')
	else:
		print('NO')


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	negatives = 0
	for i in a:
		if i < 0:
			negatives += 1
	flag = True
	for i in range(negatives - 1):
		if abs(a[i]) < abs(a[i + 1]):
			flag = False
			break
	if not flag:
		print('NO')
		continue
	for i in range(negatives, n - 1, 1):
		if abs(a[i]) > abs(a[i + 1]):
			flag = False
			break
	if not flag:
		print('NO')
	else:
		print('YES')


import sys
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	minuses = 0
	for ai in a:
		if ai < 0:
			minuses += 1
	last = float('-inf')
	possible = True
	for i in range(len(a)):
		if i < minuses:
			ai = -abs(a[i])
		else:
			ai = abs(a[i])
		if ai < last:
			possible = False
			break
		last = ai
	if possible:
		sys.stdout.write('YES\n')
	else:
		sys.stdout.write('NO\n')


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ctr = 0
	for i in range(n):
		if a[i] < 0:
			ctr += 1
			a[i] = abs(a[i])
	for i in range(ctr):
		a[i] = -a[i]
	flag = True
	for i in range(1, n):
		if a[i] < a[i - 1]:
			flag = False
			break
	if flag:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	s = 0
	m = 0
	for j in range(n):
		if l[j] < 0:
			s += 1
	for j in range(s - 1):
		if abs(l[j]) < abs(l[j + 1]):
			m = 1
			break
	if m == 0:
		for j in range(s, n - 1):
			if abs(l[j]) > abs(l[j + 1]):
				m = 1
				break
	if m == 1:
		print('NO')
	else:
		print('YES')


t = int(input())
for t_item in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	k = 0
	for x in a:
		if x < 0:
			k += 1
	flag = True
	for i in range(len(a) - 1):
		x = abs(a[i])
		y = abs(a[i + 1])
		if i < k:
			x = -x
		if i + 1 < k:
			y = -y
		if x > y:
			flag = False
			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()]
	negs = 0
	flag = 0
	for i in range(0, len(list1)):
		if list1[i] < 0:
			negs += 1
	i = 0
	while negs > 1:
		if abs(list1[i]) >= abs(list1[i + 1]):
			negs -= 1
			i += 1
		else:
			flag = 1
			break
	if negs == 1:
		i += 1
	if flag == 0:
		while i < len(list1) - 1:
			if abs(list1[i]) > abs(list1[i + 1]):
				flag = 1
				break
			i += 1
	if flag == 1:
		print('NO')
	else:
		print('YES')


from collections import deque

def sign_sort(A) -> bool:
	pos_index = deque()
	for i in range(len(A)):
		if pos_index and A[i] < 0:
			j = pos_index.popleft()
			A[j] *= -1
			A[i] *= -1
		if A[i] > 0:
			pos_index.append(i)
	past_value = float('-inf')
	for x in A:
		if x < past_value:
			return False
		past_value = x
	return True
n = int(input())
for _ in range(n):
	size = int(input())
	array_str = input()
	array = list(map(int, array_str.split(' ')))
	answer = sign_sort(array)
	if answer:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	m = [k for k in l if k < 0]
	for i in range(n):
		if i < len(m) and l[i] > 0:
			l[i] *= -1
		elif i >= len(m) and l[i] < 0:
			l[i] *= -1
	k = l.copy()
	l.sort()
	if k == l:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))[:n]
	temp = []
	neg = 0
	for i in a:
		if i < 0:
			neg += 1
	if neg == 0:
		flag = 0
		for i in range(1, n):
			if a[i] < a[i - 1]:
				print('NO')
				flag = 1
				break
		if flag == 0:
			print('YES')
	else:
		flag = 0
		for i in range(neg - 1):
			if abs(a[i]) < abs(a[i + 1]):
				print('NO')
				flag = 1
				break
		if flag == 1:
			continue
		for i in range(neg + 1, n):
			if abs(a[i]) < abs(a[i - 1]):
				print('NO')
				flag = 1
				break
		if flag == 0:
			print('YES')


n = int(input())
for i in range(n):
	x = int(input())
	l = [int(m) for m in input().split()]
	(j, k) = (0, x - 1)
	p = 0
	while k > j:
		if l[j] > 0 and l[k] < 0:
			l[j] = -l[j]
			l[k] = -l[k]
			j += 1
			k -= 1
			continue
		if l[j] < 0:
			j += 1
		if l[k] > 0:
			k -= 1
		if l[k] > 0 and l[j] < 0:
			j += 1
			k -= 1
	z = 0
	for e in range(x - 1):
		if l[e] > l[e + 1]:
			print('NO')
			z = 1
			break
	if z == 0:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	for i in a:
		if i < 0:
			cnt += 1
	abs_a = [abs(a[i]) for i in range(n)]
	for i in range(cnt):
		abs_a[i] *= -1
	if abs_a == sorted(abs_a):
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	negs = 0
	for num in arr:
		if num < 0:
			negs += 1
	for i in range(n):
		if negs > 0:
			if arr[i] > 0:
				arr[i] *= -1
			negs -= 1
		else:
			arr[i] = arr[i] if arr[i] > 0 else -arr[i]
	isSorted = True
	for i in range(1, n):
		if arr[i] < arr[i - 1]:
			isSorted = False
			break
	print('YES' if isSorted else 'NO')


for _ in range(int(input())):
	n = input()
	lst = list(map(int, input().split()))
	c = 0
	for i in range(len(lst)):
		if lst[i] < 0:
			c += 1
			lst[i] *= -1
	for i in range(len(lst)):
		if c > 0:
			lst[i] *= -1
			c -= 1
	if lst == sorted(lst):
		print('YES')
	else:
		print('NO')


tc = int(input())
for _ in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	neg_cnt = 0
	for n in a:
		if n < 0:
			neg_cnt += 1
	b = list(map(lambda x: abs(x), a))
	for i in range(neg_cnt):
		b[i] = -b[i]
	if sorted(b) == b:
		print('YES')
	else:
		print('NO')


for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	for i in a:
		if i < 0:
			cnt += 1
	b = []
	c = []
	for i in range(0, cnt):
		b.append(-abs(a[i]))
	for i in range(cnt, n):
		c.append(abs(a[i]))
	B = sorted(b)
	C = sorted(c)
	if b == B and c == C:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline

def LI():
	return list(map(int, input().split()))
for _ in range(int(input())):
	n = int(input())
	a = LI()
	flag = True
	cnt = 0
	for i in range(n):
		if a[i] < 0:
			cnt += 1
	b = []
	for i in range(n):
		if a[i] > 0 and cnt > 0:
			b.append(-a[i])
			cnt -= 1
		elif a[i] < 0 and cnt > 0:
			b.append(a[i])
			cnt -= 1
		else:
			b.append(abs(a[i]))
	tmp = b[0]
	for i in range(1, n):
		if tmp > b[i]:
			flag = False
			break
		tmp = b[i]
	if flag:
		print('YES')
	else:
		print('NO')


import sys
sys.setrecursionlimit(2 * 10 ** 5)
input = sys.stdin.readline
import math
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	narr = arr[:]
	narr.sort()
	if arr == narr:
		print('YES')
		continue
	c = 0
	for j in arr:
		if j < 0:
			c += 1
	if c == 0:
		print('NO')
		continue
	for j in range(n):
		if c > 0:
			arr[j] = -1 * abs(arr[j])
			c = c - 1
		else:
			arr[j] = abs(arr[j])
	f = 0
	for j in range(1, n):
		if arr[j] >= arr[j - 1]:
			continue
		f = 1
		break
	if f == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = [int(e) for e in input().split()]
	t = [abs(e) for e in a]
	k = a[0] > 0
	i = 0
	for i in range(1, n):
		if t[i] > t[i - 1]:
			i -= 1
			break
		k += a[i] > 0
	j = i
	while j >= 0 and t[i] == t[j]:
		j -= 1
	r = i - j
	for i in range(i + 1, n):
		if t[i] < t[i - 1]:
			print('NO')
			break
		k -= a[i] < 0
	else:
		if 0 <= k <= r:
			print('YES')
		else:
			print('NO')


for i in range(int(input())):
	a = int(input())
	lis = list(map(int, input().split()))
	c = 0
	for i in range(a):
		if lis[i] < 0:
			c += 1
			lis[i] = abs(lis[i])
	for i in range(c):
		lis[i] = -lis[i]
	l2 = lis.copy()
	l2.sort()
	if l2 == lis:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	nc = 0
	for i in range(n):
		if a[i] < 0:
			nc += 1
			a[i] = a[i] * -1
	for i in range(nc):
		a[i] = -1 * a[i]
	b = a.copy()
	b.sort()
	if a == b:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	lt = list(map(int, input().split()))
	(flag, flag1) = (0, 0)
	(l, r) = (0, n - 1)
	while l < r:
		while r > 0 and lt[r] > 0:
			r -= 1
		while l < n and lt[l] < 0:
			l += 1
		if l != n and r != 0 and (l < r):
			lt[r] *= -1
			lt[l] *= -1
			l += 1
			r -= 1
	flag = 0
	for i in range(1, n):
		if lt[i] < lt[i - 1]:
			flag = 1
	if flag == 1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	neg = 0
	for i in l:
		if i < 0:
			neg += 1
	newl = []
	for i in l:
		if neg:
			newl.append(-abs(i))
			neg -= 1
		else:
			newl.append(abs(i))
	print('YES' if newl == sorted(newl) else 'NO')


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	c = 0
	for n in l:
		if n < 0:
			c += 1
	x = [abs(i) for i in l]
	for i in range(c):
		x[i] = x[i] * -1
	if x == sorted(x):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	negative = 0
	for i in a:
		if i < 0:
			negative += 1
	b = []
	for i in a:
		if negative > 0:
			b.append(-1 * abs(i))
			negative -= 1
		else:
			b.append(abs(i))
	a = b.copy()
	a.sort()
	if a == b:
		print('YES')
	else:
		print('NO')


def check(arr):
	for i in range(len(arr) - 1):
		if arr[i] > arr[i + 1]:
			return False
	return True
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	l = 0
	h = 0
	while l < n:
		if arr[l] < 0:
			arr[l] = -1 * arr[l]
			arr[h] = -1 * arr[h]
			h += 1
		l += 1
	if check(arr):
		print('YES')
	else:
		print('NO')


t = int(input())
for __ in range(t):
	n = int(input())
	arr = [int(val) for val in input().split(' ')]
	neg_count = sum((1 if val < 0 else 0 for val in arr))
	arr = [-abs(val) if idx < neg_count else abs(val) for (idx, val) in enumerate(arr)]
	if sorted(arr) == arr:
		print('YES')
	else:
		print('NO')


tt = True
ff = False

def pif(condition):
	if condition:
		print('YES')
	else:
		print('NO')
import math
from math import ceil

def ini():
	return int(input())

def ins():
	return input()

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

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

def imat(n):
	mat = []
	for i in range(n):
		mat.append(ilist())
	return mat

def slist(n):
	slist = [input() for i in range(n)]

def rem(list, value, occurence):
	c = 0
	i = 0
	while c < occurence:
		if list[i] == value:
			list.pop(i)
			c += 1
		else:
			i += 1
t = ini()
for i in range(t):
	n = ini()
	a = ilist()
	c = 0
	for e in a:
		if e < 0:
			c += 1
	for i in range(n):
		if i < c:
			a[i] = -abs(a[i])
		else:
			a[i] = abs(a[i])
	b = a[:]
	b.sort()
	pif(a == b)


n = int(input())
for i in range(n):
	l = int(input())
	li = list(map(int, input().split()))
	neg = 0
	for i in range(l):
		if li[i] < 0:
			li[i] = -li[i]
			neg += 1
	for i in range(neg):
		li[i] = -li[i]
	s_li = sorted(li)
	if li == s_li:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	i = 0
	j = n - 1
	while i < j:
		if arr[i] <= 0:
			i += 1
		if arr[j] >= 0:
			j -= 1
		if i < j and arr[i] > 0 and (arr[j] < 0):
			arr[i] *= -1
			arr[j] *= -1
			i += 1
			j -= 1
	i = 1
	ans = 'YES'
	while i < n:
		if arr[i] < arr[i - 1]:
			ans = 'NO'
			break
		i += 1
	print(ans)


(YES, NO) = ('YES', 'NO')

def is_sorted(arr):
	for i in range(1, len(arr)):
		if arr[i] < arr[i - 1]:
			return False
	return True

def solve(n, arr):
	(i, j) = (0, 0)
	while i < n:
		if arr[i] < 0:
			arr[j] *= -1
			j += 1
			arr[i] *= -1
		i += 1
	if is_sorted(arr):
		return YES
	else:
		return NO
tc = int(input())
for _ in range(tc):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if sorted(a) == a:
		print('YES')
		continue
	ng = 0
	for i in range(n):
		if a[i] < 0:
			ng += 1
			a[i] *= -1
	for i in range(ng):
		a[i] *= -1
	print('YES' if a == sorted(a) else 'NO')


k = int(input())
for _ in range(k):
	a = int(input())
	n = list(map(int, input().split()))
	s = 0
	d = []
	for __ in n:
		if __ < 0:
			s += 1
	q = n[:s]
	w = n[s:]
	for i in q:
		e = abs(i) * -1
		d += [e]
	for j in w:
		r = abs(j)
		d += [r]
	t = sorted(d)
	if t == d:
		print('YES')
	else:
		print('NO')


def solution(arr):
	negative = len([x for x in arr if x < 0])
	for i in range(0, len(arr)):
		arr[i] = abs(arr[i])
		if negative > 0:
			arr[i] *= -1
			negative -= 1
	for i in range(0, len(arr) - 1):
		if arr[i] > arr[i + 1]:
			return 'NO'
	return 'YES'
for t in range(0, int(input())):
	_ = input()
	nums = list(map(int, input().split()))
	print(solution(nums))


from collections import deque

def is_sorted(arr):
	for i in range(len(arr) - 1):
		if arr[i + 1] < arr[i]:
			return False
	return True

def can_be_sorted(arr):
	(l, r) = (0, len(arr) - 1)
	while l < r:
		if arr[l] > 0 and arr[r] < 0:
			arr[l] *= -1
			arr[r] *= -1
			l += 1
			r -= 1
		elif arr[r] < 0:
			l += 1
		elif arr[l] > 0:
			r -= 1
		else:
			l += 1
			r -= 1
	return is_sorted(arr)
t = int(input())
for _ in range(t):
	n = input()
	arr = list(map(int, input().split(' ')))
	if can_be_sorted(arr):
		print('YES')
	else:
		print('NO')