You are given $n$ points with integer coordinates on a coordinate axis $OX$. The coordinate of the $i$-th point is $x_i$. All points' coordinates are distinct and given in strictly increasing order.

For each point $i$, you can do the following operation no more than once: take this point and move it by $1$ to the left or to the right (i..e., you can change its coordinate $x_i$ to $x_i - 1$ or to $x_i + 1$). In other words, for each point, you choose (separately) its new coordinate. For the $i$-th point, it can be either $x_i - 1$, $x_i$ or $x_i + 1$.

Your task is to determine if you can move some points as described above in such a way that the new set of points forms a consecutive segment of integers, i. e. for some integer $l$ the coordinates of points should be equal to $l, l + 1, \ldots, l + n - 1$.

Note that the resulting points should have distinct coordinates.

You have to answer $t$ independent test cases.


-----Input-----

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

The first line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of points in the set $x$.

The second line of the test case contains $n$ integers $x_1 < x_2 < \ldots < x_n$ ($1 \le x_i \le 10^6$), where $x_i$ is the coordinate of the $i$-th point.

It is guaranteed that the points are given in strictly increasing order (this also means that all coordinates are distinct). It is also guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case, print the answer — if the set of points from the test case can be moved to form a consecutive segment of integers, print YES, otherwise print NO.


-----Examples-----

Input
5
2
1 4
3
1 2 3
4
1 2 3 7
1
1000000
3
2 5 6
Output
YES
YES
NO
YES
YES


-----Note-----

None

Source: codeforces | Difficulty: EASY
Tags: Sorting

Mathematics

Complete search


Solutions:
t = int(input())
res = []
for itemT in range(t):
	n = int(input())
	x = input().split()
	iFist = int(x[0])
	iLast = int(x[-1])
	if iLast - n - iFist <= 1:
		res.append('YES')
	else:
		res.append('NO')
for itemR in res:
	print(itemR)


for s in [*open(0)][2::2]:
	a = [*map(int, s.split())]
	n = len(a)
	if a[-1] - a[0] > n + 1:
		print('NO')
		continue
	print('YES')


for s in [*open(0)][2::2]:
	a = (*map(int, s.split()),)
	print('YNEOS'[a[-1] - a[0] > len(a) + 1::2])


results = []
for _ in range(int(input())):
	n = int(input())
	array = input().split()
	if int(array[-1]) - int(array[0]) <= n + 1:
		results.append('YES')
	else:
		results.append('NO')
print('\n'.join(results))


import sys
input = sys.stdin.readline

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


from sys import stdin
from math import log, floor, ceil, gcd
from collections import defaultdict as dd
input = stdin.readline
inp = lambda : int(stdin.readline())
rs = lambda : stdin.readline().strip()

def ra(typ):
	return list(map(typ, stdin.readline().split()))

def rv(typ):
	return map(typ, stdin.readline().split())

def main():
	for _ in range(inp()):
		n = inp()
		nums = ra(int)
		n1 = 0
		d = []
		for i in range(n - 1):
			x = nums[i + 1] - nums[i]
			if x != 1:
				d.append(x)
		ans = True
		if len(d) > 2:
			ans = False
		elif len(d) == 2 and sum(d) > 4:
			ans = False
		elif len(d) == 1 and d[0] > 3:
			ans = False
		print('YES' if ans else 'NO')
main()


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


from sys import stdin, stdout

def solve():
	n = int(stdin.readline().strip())
	inputs = list(map(int, stdin.readline().strip().split(' ')))
	max_blanks = 0
	count_blank1 = 0
	for i in range(1, n):
		diff = inputs[i] - inputs[i - 1] - 1
		if diff > 2:
			print('NO')
			return
		elif diff == 2:
			if max_blanks == 2 or max_blanks == 1:
				print('NO')
				return
			else:
				max_blanks = 2
		elif diff == 1:
			count_blank1 += 1
			if max_blanks == 2:
				print('NO')
				return
			elif max_blanks == 1:
				if count_blank1 > 2:
					print('NO')
					return
			else:
				max_blanks = 1
	print('YES')

def main():
	t = int(stdin.readline())
	for _ in range(t):
		solve()
main()


tests = int(input())
out = ''
for _ in range(tests):
	size = int(input())
	seq = [int(x) for x in input().split()]
	last = seq[0]
	canMove = True
	for x in seq[1:]:
		dif = x - last
		if dif > 3:
			break
		elif dif == 3:
			if not canMove:
				break
			last = x - 1
			canMove = False
		elif dif == 2:
			if not canMove:
				last = x - 1
			else:
				last = x
			canMove = False
		elif dif == 1:
			last = x
	else:
		out += 'YES\n'
		continue
	out += 'NO\n'
print(out)


import sys, math
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = []
	for i in range(n - 1):
		a.append(l[i + 1] - l[i])
	else:
		d = a.count(2)
		t = a.count(3)
		z = a.count(1)
		if t + d + z != n - 1:
			print('NO')
		elif t == 1 and d == 0:
			print('YES')
		elif (d == 1 or d == 2 or d == 0) and t == 0:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	a = input().split()
	x = int(a[0])
	y = int(a[-1])
	if y - x > n + 1:
		print('NO')
	else:
		print('YES')


n = int(input())
out = []
for i in range(n):
	x = int(input())
	l = [int(i) for i in input().split()]
	if x == 1:
		out.append('YES')
		continue
	if x > 1:
		prev = l[0]
		m = 0
		check = 0
		for i in l:
			if i - prev > 3:
				m = 1
				out.append('NO')
				break
			if i - prev > 1:
				check += i - prev
			if check > 4:
				m = 1
				out.append('NO')
				break
			prev = i
	if m == 0:
		out.append('YES')
for i in out:
	print(i)


from shutil import move
N = int(input())

def solve(s):
	now = s[0]
	move = False
	for c in s:
		if c - now <= 1:
			now = c
		elif c - now == 2:
			now = c - 1
		elif c - now == 3 and (not move):
			now = c - 1
			move = True
		else:
			print('NO')
			return
	print('YES')
q = []
for i in range(N):
	s = input()
	l = [int(i) for i in input().split()]
	q.append(l)
for s in q:
	solve(s)


import math
q = int(input())
for z in range(0, q):
	n = int(input())
	s = input()
	s = s.split()
	if int(s[-1]) - int(s[0]) > n + 1:
		print('NO')
	else:
		print('YES')


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


import sys

def solve():
	n = int(input())
	arr = [int(x) for x in input().split()]
	if arr[n - 1] - arr[0] <= n + 1:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	solve()


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


T = input()
for i in range(int(T)):
	length = input()
	arr = input()
	arr = arr.split(' ')
	if int(arr[len(arr) - 1]) - int(arr[0]) < int(length) + 2:
		print('YES')
	else:
		print('NO')


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


t = int(input())
odg = ['NO'] * t
for i in range(t):
	n = int(input())
	br = list(map(int, input().split(' ')))
	dvice = 0
	trice = 0
	alarm = 0
	for j in range(1, n):
		razlika = br[j] - br[j - 1]
		if razlika == 2:
			dvice += 1
		elif razlika == 3:
			trice += 1
		elif razlika > 3:
			alarm = 1
			break
	if alarm == 0:
		if dvice <= 2 and trice == 0 or (dvice == 0 and trice == 1) or (dvice == 0 and trice == 0):
			odg[i] = 'YES'
for i in odg:
	print(i)


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


def main():
	tests = int(input())
	while tests > 0:
		n = int(input())
		array = [int(x) for x in input().split(' ')]
		if array[-1] - array[0] - n + 1 > 2:
			print('NO')
		else:
			print('YES')
		tests -= 1
main()


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	if a[-1] <= a[0] + n - 1 + 2:
		print('YES')
	else:
		print('NO')


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


def eval(dots):
	lens = []
	for i in range(1, len(dots)):
		lens.append(dots[i] - dots[i - 1])
	if max(lens) > 3:
		return 'NO'
	elif max(lens) == 3 and 2 not in lens and (lens.count(3) == 1):
		return 'YES'
	elif max(lens) == 2 and lens.count(2) < 3:
		return 'YES'
	elif max(lens) == 1:
		return 'YES'
	else:
		return 'NO'

def main():
	n = int(input())
	dots = []
	for i in range(n):
		c = int(input())
		temp = list(map(int, input().split()))
		dots.append(temp)
	for dot in dots:
		if len(dot) > 1:
			print(eval(dot))
		else:
			print('YES')
main()


a = int(input())
for _ in range(a):
	k = 1
	b = int(input())
	c = list(map(int, input().split()))
	if c[-1] - c[0] > b + 1:
		print('NO')
	else:
		print('YES')
	k = 1


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split(' ')]
	ans = 'YES'
	if l[-1] - l[0] - n + 1 >= 3:
		ans = 'NO'
	print(ans)


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


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


for i in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	print('YNEOS'[a[-1] - a[0] > len(a) + 1::2])


def solve():
	n = int(input())
	a = list(map(int, input().split(' ')))
	print('YES' if a[-1] - a[0] - n + 1 <= 2 else 'NO')
for t in range(int(input())):
	solve()


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


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


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print('YNEOS'[l[-1] - l[0] > len(l) + 1::2])


T = int(input())
for t in range(T):
	n = int(input())
	v = list(map(int, input().split()))
	if v[n - 1] - v[0] - 1 <= n:
		print('YES')
	else:
		print('NO')


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


def Dist():
	a = int(input())
	num_arr = input().split()
	num_arr = list(map(int, num_arr))
	if num_arr[a - 1] - num_arr[0] <= a + 1:
		print('YES')
	else:
		print('NO')
num_iter = int(input())
for _ in range(num_iter):
	Dist()


t = int(input())
for i in range(t):
	n = int(input())
	s = [int(i) for i in input().split()]
	f = 'YES'
	if s[-1] - s[0] > n + 1:
		f = 'NO'
	print(f)