Read problems statements in Mandarin Chinese and Russian as well. 

Given a sequence of n distinct numbers a[1..n], we want to sort them in an ascending order.

An interesting property of some sequences is that all numbers are almost at their correct position! More formally, the distance between the current position of any value is at most 1 from its correct position in a sorted order.

Now, you want to verify whether the input sequence has such a property.

Note that the time limit for this problem is 0.2 seconds. Please try to write a very efficient algorithm and implementation.

------ Input ------ 

The first line contains an integer T denoting the total number of test cases.
For each test case, the first line contains a single integer n, and the second line contains a[1..n] as a single space-separated list.

------ Output ------ 

For each test case, output "YES" or "NO" (without quotes) to indicate whether the input sequence has such a property.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ n ≤ 10^{6}$
$1 ≤ a[i] ≤ 10^{9}$

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

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	fl = True
	for i in range(n - 2):
		if arr[i] > arr[i + 2]:
			fl = False
			break
	if fl:
		print('YES')
	else:
		print('NO')


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


def sorting(n, lst):
	count = 0
	for i in range(n - 2):
		if lst[i] > lst[i + 1] and lst[i] > lst[i + 2]:
			count = 1
			return 'NO'
	if count == 0:
		return 'YES'
t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().strip().split()))[:n]
	print(sorting(n, lst))


def Test(n, arr):
	last = arr[n - 1]
	flag = 0
	for i in range(n - 2):
		if arr[i] > arr[i + 1] and arr[i] > arr[i + 2]:
			return 'NO'
	return 'YES'
for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	print(Test(n, s))


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


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n < 3:
		print('YES')
	else:
		f = 0
		for i in range(n - 2):
			if a[i] > a[i + 1] and a[i] > a[i + 2]:
				f = 1
				break
		if f == 0:
			print('YES')
		else:
			print('NO')


def lisin():
	a = list(map(int, input().split()))
	return a
for tastcas in range(int(input())):
	n = int(input())
	a = lisin()
	if n < 3:
		print('YES')
	else:
		f = 0
		for i in range(n - 2):
			if a[i] > a[i + 1] and a[i] > a[i + 2]:
				f = 1
				break
		if f == 0:
			print('YES')
		else:
			print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	flag = True
	for i in range(n - 2):
		if l[i] > l[i + 2]:
			flag = False
			break
	if flag:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	input()
	arr = [int(x) for x in input().strip().split()]
	flag = 0
	result = 'YES'
	for i in range(1, len(arr)):
		if arr[i - 1] > arr[i]:
			if flag == 1:
				result = 'NO'
				break
			(arr[i - 1], arr[i]) = (arr[i], arr[i - 1])
			flag = 1
		else:
			flag = 0
	print(result)