Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a sequence $A_{1}, A_{2}, \ldots, A_{N}$. You may perform the following operation any number of times: select any two adjacent elements $A_{i}$ and $A_{i + 1}$ and replace one of them with $\frac{A_{i} + A_{i + 1}}{2}$ (a real number, i.e. without rounding). You may also select each pair of adjacent elements and each element to replace in multiple operations, i.e. any number of times.

Is it possible to make the sequence strictly increasing in a finite number of operations?

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing the string "Yes" if it is possible to make the sequence strictly increasing or "No" otherwise (without quotes).

You may print each character of each string in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

------  Constraints  ------
$1 ≤ T ≤ 50,000$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
4
2
7 4
3
1 2 2
5
5 5 5 5 5
8
7 2 4 1 6 8 3 9
----- Sample Output 1 ------ 
No
Yes
No
Yes
----- explanation 1 ------ 
Example case 1: Clearly, after any sequence of operations, $A_{1} > A_{2}$ holds, so it is impossible to make the sequence strictly increasing.

Example case 2:  Choose $A_{1}$ and $A_{2}$ and change $A_{2}$ to $\frac{1+2}{2}$. The sequence after this operation is $[1, 1.5, 2]$, which is a strictly increasing sequence. 

There may also be other valid sequences of operations that give a strictly increasing sequence.

Example case 3: No matter which pair of adjacent elements we choose, we can only change one of them to $\frac{5+5}{2} = 5$, so the sequence always remains $[5, 5, 5, 5, 5]$.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	(i, keep_loopin) = (1, True)
	while i < n and keep_loopin:
		if a[i] > a[i - 1]:
			keep_loopin = False
		i += 1
	if keep_loopin:
		print('No')
	else:
		print('Yes')
	t -= 1


import os.path
from math import gcd, floor, ceil, log2
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

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

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	n = inp()
	a = li()
	f = False
	for i in range(n - 1):
		if a[i] < a[i + 1]:
			f = True
			break
	if f == True:
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for i in range(n - 1):
		if a[i + 1] > a[i]:
			count = 1
			break
	if count == 1:
		print('Yes')
	else:
		print('No')


y = int(input())
for i in range(y):
	n = int(input())
	yush = list(map(int, input().split()))
	count = 0
	for j in range(1, n):
		if yush[j] > yush[j - 1]:
			count += 1
	print('Yes' if count > 0 else 'No')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	for j in range(1, n):
		if l[j] > l[j - 1]:
			c += 1
	print('Yes' if c > 0 else 'No')


try:
	for t in range(int(input())):
		N = int(input())
		A = list(map(int, input().split()))
		res = True
		for i in range(0, N - 1):
			if A[i] < A[i + 1]:
				res = False
				break
		if res == True:
			print('No')
		else:
			print('Yes')
except:
	pass


def check(arr):
	flag = 0
	for i in range(len(arr) - 1):
		if arr[i] >= arr[i + 1]:
			flag = 1
		else:
			flag = 0
			break
	if flag == 0:
		print('Yes')
	else:
		print('No')
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	check(arr)


def isInc(arr):
	for i in range(0, len(arr) - 1):
		if arr[i] <= arr[i + 1]:
			continue
		else:
			return False
	return True

def isDec(arr):
	for i in range(0, len(arr) - 1):
		if arr[i] >= arr[i + 1]:
			continue
		else:
			return False
	return True

def isEqual(arr):
	for i in range(0, len(arr) - 1):
		if arr[i] == arr[i + 1]:
			continue
		else:
			return False
	return True
t = int(input())
while t:
	t -= 1
	n = int(input())
	x = [int(i) for i in input().split()]
	if isInc(x) and (not isEqual(x)):
		print('Yes')
	elif isDec(x):
		print('No')
	elif isEqual(x):
		print('No')
	else:
		print('Yes')


for u in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	f = 0
	for i in range(n - 1):
		if l[i] < l[i + 1]:
			f = 1
			break
	if f == 1:
		print('Yes')
	else:
		print('No')


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


def solve():
	try:
		n = int(input())
		l1 = list(map(int, input().split()))
	except:
		pass
	cnt = 0
	for i in range(n - 1):
		if l1[i] >= l1[i + 1]:
			cnt += 1
	if cnt == n - 1:
		print('No')
	else:
		print('Yes')
try:
	for tc in range(int(input())):
		solve()
except:
	pass


n = int(input())
for i in range(n):
	n1 = int(input())
	l1 = list(map(int, input().split()))
	f = 'No'
	for i in range(n1 - 1):
		if l1[i] < l1[i + 1]:
			f = 'Yes'
	print(f)


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = l1.copy()
	l2.sort(reverse=True)
	if l1 == l2:
		print('No')
	else:
		print('Yes')


T = int(input())
for i in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	flag = False
	for i in range(n - 1):
		if arr[i] < arr[i + 1]:
			flag = True
	if flag:
		print('Yes')
	else:
		print('No')


import sys
sys.setrecursionlimit(10 ** 5 + 1)
inf = int(10 ** 20)
max_val = inf
min_val = -inf
RW = lambda : sys.stdin.readline().strip()
RI = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]
for _ in range(RI()):
	lens = RI()
	arrs = RMI()
	possible = 'No'
	for i in range(1, lens):
		if arrs[i] > arrs[i - 1]:
			possible = 'Yes'
			break
	print(possible)


T = int(input())
for i in range(0, T):
	N = int(input())
	A = list(map(int, input().split()))
	c = 0
	i1 = 1
	while i1 < N:
		if A[i1] > A[i1 - 1]:
			c = c + 1
			i1 = N
		i1 = i1 + 1
	if c == 1:
		print('Yes')
	else:
		print('No')


from sys import stdin, stdout

def decreasing(arr, n):
	for i in range(1, n):
		if arr[i] > arr[i - 1]:
			return False
	return True
for test in range(int(stdin.readline())):
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().rsplit()))
	if decreasing(arr, n):
		print('No')
	else:
		print('Yes')


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	for j in range(len(arr) - 1):
		if arr[j] < arr[j + 1]:
			print('Yes')
			break
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	flag = False
	for i in range(len(arr) - 1):
		if arr[i] < arr[i + 1]:
			flag = True
			break
	if flag:
		print('Yes')
	else:
		print('No')


import numpy as np
for _ in range(int(input())):
	n = int(input())
	arr = np.array(list(map(int, input().split())))
	flag = False
	for i in range(arr.size - 1):
		if arr[i] < arr[i + 1]:
			flag = True
			break
	if flag:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	ans = False
	for i in range(n - 1):
		if l[i] < l[i + 1]:
			ans = True
			break
	if ans:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a, reverse=True)
	if a == b:
		print('No')
	elif b[0] == b[-1]:
		print('No')
	else:
		print('Yes')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print('Yes') if any((arr[i] < arr[i + 1] for i in range(n - 1))) else print('No')


for _ in range(int(input())):
	n = int(input())
	p = 0
	l = list(map(int, input().split()))
	for i in range(n - 1):
		if l[i] >= l[i + 1]:
			p += 1
	if p + 1 == n:
		print('No')
	else:
		print('Yes')


t = int(input())
while t:
	t -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	ar1 = arr.copy()
	ar1.sort(reverse=True)
	se = set(arr)
	if len(arr) == 1:
		print('Yes')
	elif len(se) == 1:
		print('No')
	elif ar1 == arr:
		print('No')
	else:
		print('Yes')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	temp = arr[0]
	q = 0
	for i in range(0, len(arr) - 1):
		if arr[i + 1] <= arr[i]:
			continue
		else:
			q = 1
			break
	if q == 1:
		print('Yes')
	else:
		print('No')


bigno = 1000000001
bigno2 = 1000000000000000001
t = int(input())
for i in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	a = len(set(A))
	if a == 1:
		print('No')
		continue
	b = 0
	for i in range(N - 1):
		if A[i] < A[i + 1]:
			print('Yes')
			b = 1
			break
	if b == 0:
		print('No')


for _ in range(int(input())):
	n = int(input())
	a_n = list(map(int, input().split()[:n]))
	ok = False
	for i in range(n - 1):
		if a_n[i] < a_n[i + 1]:
			ok = True
	if ok:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	__ = int(input())
	___ = list(map(int, input().split()))
	print('No' if all((____ >= _____ for (____, _____) in zip(___, ___[1:]))) else 'Yes')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ctr = 0
	for i in range(len(a) - 1):
		if a[i] < a[i + 1]:
			ctr += 1
		else:
			continue
	if ctr != 0:
		print('Yes')
	else:
		print('No')


for t in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	if a[::-1] == sorted(a):
		print('No')
	else:
		print('Yes')


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	flag = 0
	for j in range(n - 1):
		if arr[j] < arr[j + 1]:
			flag = 1
	if flag == 0:
		print('No')
	else:
		print('Yes')


t = int(input())
while t:
	t = t - 1
	k = int(input())
	n = list(map(int, input().split()))
	if len(set(n)) == 1 or sorted(n, reverse=True) == n:
		print('No')
	else:
		print('Yes')


t = int(input())
for _ in range(t):
	n = int(input())
	nums = [int(i) for i in input().split()]
	doable = False
	for i in range(1, len(nums)):
		if nums[i] - nums[i - 1] > 0:
			doable = True
	if doable:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	nums = [int(x) for x in input().split(' ')]
	if len(set(nums)) == 1:
		print('No')
	else:
		flag = 0
		for i in range(len(nums) - 1):
			if nums[i] < nums[i + 1]:
				flag = 1
				break
		if flag == 0:
			print('No')
		else:
			print('Yes')


T = int(input())
for _ in range(T):
	N = int(input())
	li = list(map(int, input().strip().split()))
	a = li.copy()
	a.sort(reverse=True)
	if li == a:
		print('No')
	else:
		print('Yes')


def allequal(lst):
	a = lst[0]
	count = 0
	for i in lst:
		if a == i:
			count += 1
	if count == len(lst):
		return True
	return False
for t in range(int(input())):
	a = int(input())
	val = list(map(int, input().split()))
	if val == sorted(val, reverse=True) or allequal(val):
		print('No')
	else:
		print('Yes')


for _ in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	flag = 0
	for i in range(1, len(list1)):
		if list1[i] > list1[i - 1]:
			flag = 1
	print('Yes') if flag == 1 else print('No')