There are N people participating in a race. The N^{th} participant is your friend, so you want him to win. You are not a man of ethics, so you decided to inject some units of a Performance Enhancement Drug (don't ask where that came from) in your friend's body.

From the charts, you came to know the speed of every player. Formally, for a player i, his speed is denoted by S_{i}. 
The change in speed with one unit of the drug is K units. Note that K can be negative, which means the drug has more side effects than benefits.
Of course, there will be a drug test before the race, so your friend will be caught if the number of units of the drug in his blood is greater than or equal to L.

You need to determine whether you can help your friend to win the race (with or without drugs), without getting caught.

Note: A player wins the race if he has the maximum speed among all the participants. If there are more than one people with a maximal speed, they tie at first place, and no one wins!

------ Input Format ------ 

- First line will contain a single integer T, the number of test cases. Description of the test cases follows.
- First line of each test case will contain three space-separated integers, N - the number of participants, K - the change in speed with one unit of the drug, and L - minimum units of the drug that can be detected in the drug test.
- Second line of each test case will contain N space-separated integers S_{i}, the speeds of the participants.

------ Output Format ------ 

For each test case print "Yes" if you can help your friend to win the race, otherwise "No" in a single line.

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

$1 ≤ T ≤ 200$
$1 ≤ N, L ≤ 1000$
$-1000 ≤K ≤1000$
$1 ≤ S_{i} ≤ 1000$

----- Sample Input 1 ------ 
3
4 2 2
2 1 3 2
4 2 2
2 1 4 2
3 -10 100
12 11 9
----- Sample Output 1 ------ 
Yes
No
No
----- explanation 1 ------ 
- In test case $1$, initial speeds are $\{2, 1, 3, 2\}$. You can inject $1$ unit of the drug into your friend's body, and increase his speed from $2$ to $4$. $4$ is the fastest speed, thus you helped your friend win the race. Hence, the answer is "Yes".
- In test case $2$, initial speeds are $\{2, 1, 4, 2\}$. You can inject $1$ unit of the drug into your friend's body, and increase his speed from $2$ to $4$. But you can not inject any more units of the drug, and with speed $4$ your friend can only tie at rank $1$ and not Win. Hence, the answer is "No".
- In test case $3$, initial speeds are $\{12, 11, 9\}$. Note that the impact of the drug in this case is negative, which means that the speed will only decrease if you inject it. So, there is no way you can help your friend to win. Hence, the answer is "No".

Difficulty: MEDIUM
Tags: Greedy algorithms

Constructive algorithms

Mathematics

Ad-hoc
Skill types: Greedy algorithms

Starter code:

Solutions:
for i in range(int(input())):
	(n, k, l) = map(int, input().split())
	speeds = list(map(int, input().split()))
	if max(speeds) == speeds[-1]:
		print('Yes')
	elif k <= 0 and max(speeds) != speeds[-1]:
		print('No')
	elif int((max(speeds) - speeds[-1]) / k) + 1 >= l:
		print('No')
	else:
		print('Yes')


t = int(input())
yur = []
for iir in range(0, t):
	a = str(input())
	a = a.strip()
	iit = a.split(' ')
	hr = []
	for ffc in iit:
		hr.append(int(ffc))
	ase = str(input())
	ase = ase.strip()
	yye = ase.split(' ')
	ppr = []
	for nnxz in yye:
		ppr.append(int(nnxz))
	wwq = [hr, ppr]
	yur.append(wwq)
for bxsw in yur:
	a = bxsw[0]
	b = bxsw[1]
	m = a[-1] - 1
	up = a[1]
	gg = up * m
	yyr = b[-1]
	hu = {}
	ume = 0
	for uuew in b:
		if uuew > ume:
			ume = uuew
		if uuew not in hu:
			hu[uuew] = 1
		else:
			hu[uuew] += 1
	if ume == yyr and hu[ume] == 1:
		print('Yes')
	elif gg < 0:
		print('No')
	elif ume == yyr:
		print('Yes')
	else:
		ynrt = ume - yyr
		if gg > ynrt:
			print('Yes')
		else:
			print('No')


t = int(input())
while t > 0:
	(n, k, l) = map(int, input().split())
	arr = list(map(int, input().split()))
	if n == 1:
		print('Yes')
	else:
		sp = arr[len(arr) - 1]
		del arr[len(arr) - 1]
		mx = max(arr)
		if mx < sp:
			print('Yes')
		elif k <= 0 and mx >= sp:
			print('No')
		else:
			sp += (l - 1) * k
			if mx < sp:
				print('Yes')
			else:
				print('No')
	t -= 1


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	a = [int(i) for i in input().split()]
	if n == 1:
		print('Yes')
	else:
		f = a[-1]
		b = max(a[:-1])
		ans = 'No'
		if f > b or f + (l - 1) * k > b:
			ans = 'Yes'
		print(ans)


t = int(input())
for i in range(t):
	s = []
	(n, k, l) = map(int, input().split())
	s = list(map(int, input().split()))
	cs = s[-1]
	if n == 1:
		print('Yes')
	elif cs + k * (l - 1) > max(s):
		print('Yes')
	else:
		print('No')


test_cases = int(input())
for _ in range(test_cases):
	(N, K, L) = input().split()
	(N, K, L) = (int(N), int(K), int(L))
	A = list(map(int, input().split()))
	if N == 1:
		print('Yes')
	else:
		friend = A[-1]
		del A[-1]
		mx = max(A)
		if friend > mx:
			print('Yes')
		elif K < 0 and mx >= friend:
			print('No')
		else:
			sum1 = friend + (L - 1) * K
			if sum1 > mx:
				print('Yes')
			else:
				print('No')


import math
for tc in range(int(input())):
	(n, k, l) = map(int, input().split())
	s = list(map(int, input().split()))
	poss = True
	curspeed = s[-1]
	maxspeed = 0
	for i in range(n - 1):
		maxspeed = max(maxspeed, s[i])
	req = maxspeed - curspeed + 1
	if req > 0:
		if k > 0:
			rk = math.ceil(req / k)
			if rk >= l:
				poss = False
		else:
			poss = False
	print('Yes' if poss else 'No')


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	(*a, f) = map(int, input().split())
	if n == 1:
		print('Yes')
		continue
	if k < 1:
		print('Yes' if f > max(a) else 'No')
	else:
		print('Yes' if f + k * (l - 1) > max(a) else 'No')


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	arr = list(map(int, input().split()))
	if n == 1:
		print('Yes')
	else:
		s = arr[n - 1]
		del arr[n - 1]
		m = max(arr)
		if m < s:
			print('Yes')
		elif k <= 0 and m >= s:
			print('No')
		else:
			s += (l - 1) * k
			if m < s:
				print('Yes')
			else:
				print('No')


t = int(input())
for i in range(t):
	(n, k, l) = map(int, input().split())
	arr = list(map(int, input().split()))
	if n == 1:
		print('Yes')
	else:
		sp = arr[len(arr) - 1]
		del arr[len(arr) - 1]
		mx = max(arr)
		if mx < sp:
			print('Yes')
		elif k <= 0 and mx >= sp:
			print('No')
		else:
			sp += (l - 1) * k
			if mx < sp:
				print('Yes')
			else:
				print('No')


for _ in range(int(input())):
	(n, k, l) = map(int, input().split(' '))
	s = list(map(int, input().split(' ')))
	spd = s[-1]
	unt = 1
	if spd == max(s) and s.count(spd) == 1:
		print('Yes')
	else:
		while unt < l:
			spd = spd + k
			if spd > max(s):
				print('Yes')
				break
			unt += 1
		if spd <= max(s):
			print('No')


t = int(input())
for _ in range(t):
	(n, k, l) = map(int, input().split())
	lst = list(map(int, input().split()))
	if n == 1:
		print('Yes')
		continue
	fv = lst[-1]
	del lst[-1]
	mx = max(lst)
	if fv > mx:
		print('Yes')
	elif k <= 0:
		print('No')
	else:
		val = fv + k * (l - 1)
		if val > mx:
			print('Yes')
		else:
			print('No')


t = int(input())
for t in range(t):
	(n, k, l) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	f_s = arr[n - 1]
	del arr[n - 1]
	if n == 1:
		print('Yes')
	else:
		if k > 0:
			f_s = f_s + k * (l - 1)
		if f_s > max(arr):
			print('Yes')
		else:
			print('No')


for _ in range(int(input())):
	(N, K, L) = list(map(int, input().split()))
	peoples = list(map(int, input().split()))
	lit = []
	lit.append(peoples[-1])
	peoples.remove(peoples[-1])
	if len(peoples) == 0:
		print('Yes')
	else:
		lit.append(max(peoples))
		if lit[0] > lit[1]:
			print('Yes')
		else:
			lit[0] += K * (L - 1)
			if lit[0] > lit[1]:
				print('Yes')
			else:
				print('No')


t = int(input())
for i in range(t):
	(n, k, l) = input().split()
	n = int(n)
	k = int(k)
	l = int(l)
	A = [int(x) for x in input().split()]
	if n == 1:
		print('Yes')
	else:
		x = A[n - 1]
		B = A[:n - 1]
		m = max(B)
		if x > m:
			print('Yes')
		elif x + (l - 1) * k > m:
			print('Yes')
		else:
			print('No')


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	a = list(map(int, input().split()))
	b = max(a)
	if a[n - 1] == b and a.count(b) == 1:
		print('Yes')
		continue
	f = a[n - 1]
	f = f + k * (l - 1)
	if f > b:
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	(n, k, l) = map(int, input().split())
	X = list(map(int, input().split()))
	if k <= 0:
		if X.count(max(X)) >= 2:
			print('No')
		elif max(X) != X[-1]:
			print('No')
		else:
			print('Yes')
	elif max(X) >= X[-1] + k * (l - 1):
		print('No')
	else:
		print('Yes')


t = int(input())
for _ in range(t):
	(ttl_pla, booster, limit) = map(int, input().split())
	pla = list(map(int, input().split()))
	my_max = max(pla)
	if pla.count(my_max) == 1 and my_max == pla[-1]:
		print('Yes')
	else:
		valid_intake = 0
		if 1 < booster:
			valid_intake = limit * (booster - 1)
		if my_max < pla[-1] + valid_intake:
			print('Yes')
		else:
			print('No')


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	s = list(map(int, input().split()))
	if n > 1:
		mx = max(s[:n - 1])
	else:
		print('Yes')
		continue
	if s[-1] > mx:
		print('Yes')
		continue
	elif s[-1] + k * (l - 1) > mx:
		print('Yes')
	else:
		print('No')


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


t = int(input())
for _ in range(t):
	i = 0
	(n, k, l) = map(int, input().split())
	sp = [int(w) for w in input().split()]
	f = sp[-1]
	m = max(sp)
	if n == 1:
		print('Yes')
	elif m < f:
		print('No')
	elif not k <= 0:
		while i < l - 1:
			f = f + k
			i = i + 1
			if f > m:
				print('Yes')
				break
		else:
			print('No')
	else:
		print('No')


import sys
from math import gcd, sqrt, log, ceil, floor
tc = int(input().strip())
for t in range(tc):
	(n, k, l) = map(int, input().split())
	speeds = list(map(int, input().split()))
	if max(speeds) == speeds[n - 1] and k <= 0:
		if speeds.count(max(speeds)) > 1:
			print('No')
		else:
			print('Yes')
	else:
		speeds[n - 1] += k * (l - 1)
		if max(speeds) == speeds[n - 1]:
			if speeds.count(max(speeds)) > 1:
				print('No')
			else:
				print('Yes')
		else:
			print('No')


t = int(input())
for i in range(t):
	(n, k, l) = map(int, input().split())
	arr = list(map(int, input().split()))
	arrr = arr.copy()
	arrr.pop(n - 1)
	if n == 1:
		print('Yes')
		continue
	if max(arr[n - 1] + k * (l - 1), arr[n - 1]) > max(arrr):
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	(n, k, l) = list(map(int, input().split()))
	speeds = list(map(int, input().split()))
	m = max(speeds)
	f = speeds[-1]
	if f + (l - 1) * k > m or (f == m and speeds.count(m) == 1):
		print('Yes')
	else:
		print('No')


t = input()
for c in range(0, int(t)):
	(n, k, l) = input().split()
	a = input().split()
	arr = []
	noneed = 1
	for x in a:
		arr.append(int(x))
	for y in range(0, int(n) - 1):
		if arr[int(n) - 1] <= arr[y]:
			noneed = 0
	if noneed == 1:
		print('Yes')
	elif arr[int(n) - 1] + int(k) * (int(l) - 1) > max(arr):
		print('Yes')
	else:
		print('No')


for i in range(int(input())):
	(N, K, L) = map(int, input().split())
	S = list(map(int, input().split()))
	friend = S[N - 1]
	if K <= 0:
		if max(S) == S[N - 1]:
			print('Yes')
		else:
			print('No')
	else:
		friend += (L - 1) * K
		if friend > max(S):
			print('Yes')
		else:
			print('No')


for i in range(int(input())):
	(n, k, l) = map(int, input().split())
	S = list(map(int, input().split()))
	f = S[n - 1]
	m = max(S)
	if f == m:
		print('Yes')
	else:
		if k > 0:
			f += k * (l - 1)
		if f > m:
			print('Yes')
		else:
			print('No')


t = int(input())
for i in range(t):
	(n, k, l) = map(int, input().split())
	S = list(map(int, input().split()))
	friend_speed = S[n - 1]
	friend_speed = max(friend_speed, friend_speed + (l - 1) * k)
	race_over = False
	del S[n - 1]
	for item in S:
		if item >= friend_speed and race_over is False:
			race_over = True
		else:
			continue
	if race_over is True:
		print('No')
	else:
		print('Yes')


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	s = list(map(int, input().split()))
	s_f = s[n - 1]
	maxi = max(s)
	if s_f == maxi:
		print('Yes')
	else:
		s_f += (l - 1) * k
		if s_f > maxi:
			print('Yes')
		else:
			print('No')


get_int = lambda : int(input())
get_mint = lambda : list(map(int, input().split()))
for _ in range(get_int()):
	(N, K, L) = get_mint()
	S = get_mint()
	if N == 1 or S[-1] > max(S[:-1]):
		print('Yes')
		continue
	if K < 1 or L < 2:
		print('No')
		continue
	if K * (L - 1) + S[-1] > max(S[:-1]):
		print('Yes')
	else:
		print('No')


for t in range(int(input())):
	(n, k, l) = [int(x) for x in input().split(' ')]
	S = [int(x) for x in input().split(' ')]
	if n == 1:
		print('Yes')
		continue
	friend = S[-1]
	S = S[:-1]
	best = max(S)
	if friend > best:
		print('Yes')
		continue
	new_speed = friend + k * (l - 1)
	if new_speed > best:
		print('Yes')
	else:
		print('No')


import math
for _ in range(int(input())):
	(N, K, L) = list(map(int, input().split()))
	S = list(map(int, input().split()))
	maxval = 0
	maxindex = 0
	for i in range(len(S)):
		if S[i] > maxval:
			maxval = S[i]
			maxindex = i
	if maxindex == len(S) - 1:
		print('Yes')
		continue
	if K <= 0:
		print('No')
		continue
	if math.ceil((maxval + 1 - S[-1]) / K) < L:
		print('Yes')
		continue
	print('No')


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	s = list(map(int, input().split()))
	if n == 1:
		print('Yes')
	else:
		d = s[n - 1]
		s.pop()
		a = max(s)
		if a < d:
			print('Yes')
		elif k <= 0 and a >= d:
			print('No')
		else:
			total = d + k * (l - 1)
			if total > a:
				print('Yes')
			else:
				print('No')


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	a = list(map(int, input().split()))
	if n == 1:
		print('Yes')
		continue
	b = a.pop()
	ma = max(a)
	if b > ma:
		print('Yes')
	elif b + k * (l - 1) > ma:
		print('Yes')
	else:
		print('No')


t = int(input())
while t:
	(n, k, l) = map(int, input().split())
	ls = list(map(int, input().split()))
	if n == 1:
		print('Yes')
	else:
		mx = max(ls[:-1])
		if mx < ls[-1]:
			print('Yes')
		elif k > 0:
			if mx - ls[-1] < (l - 1) * k:
				print('Yes')
			else:
				print('No')
		else:
			print('No')
	t -= 1


for I in range(int(input())):
	(n, k, l) = map(int, input().split())
	a = list(map(int, input().split()))
	last = a[-1]
	if k < 0:
		if a[-1] >= max(a):
			print('Yes')
		else:
			print('No')
	else:
		for i in range(l - 1):
			last += k
		if last > max(a):
			print('Yes')
		else:
			print('No')


for x in range(int(input())):
	(n, k, l) = [int(d) for d in input().split()]
	a = [int(d) for d in input().split()]
	m = max(a)
	my = a[-1]
	if k < 0:
		if a[-1] >= m:
			print('Yes')
		else:
			print('No')
	else:
		for i in range(l - 1):
			my += k
		if my > m:
			print('Yes')
		else:
			print('No')


t = int(input())
while t:
	(a, b, c) = map(int, input().split(' '))
	n = list(map(int, input().split(' ')))
	m = max(n)
	if m == n[-1]:
		print('Yes')
	elif b < 1:
		print('No')
	elif b > 0:
		p = b * (c - 1) + n[-1]
		if p > m:
			print('Yes')
		else:
			print('No')
	t = t - 1


t = int(input())
for i in range(t):
	(n, k, l) = map(int, input().split(' '))
	s = list(map(int, input().split(' ')))
	friend = s[-1]
	maxspeed = max(s)
	if friend == maxspeed:
		print('Yes')
	elif k < 1:
		print('No')
	elif k > 0:
		s[-1] += k * (l - 1)
		if s[-1] > maxspeed:
			print('Yes')
		else:
			print('No')


for _ in range(int(input())):
	(n, k, l) = map(int, input().split(' '))
	speeds = list(map(int, input().split(' ')))
	frnd = speeds[-1]
	maxs = max(speeds)
	if frnd == maxs:
		print('Yes')
	elif k < 1:
		print('No')
	elif k > 0:
		speeds[-1] += k * (l - 1)
		if speeds[-1] > maxs:
			print('Yes')
		else:
			print('No')


from math import ceil
for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	arr = list(map(int, input().split()))
	if n == 1:
		print('Yes')
		continue
	maxi = max(arr[:len(arr) - 1])
	frnd = arr[-1]
	diff = maxi - frnd
	if diff < 0:
		print('Yes')
		continue
	if k <= 0:
		print('No')
		continue
	diff += 1
	drug = ceil(diff / k)
	if drug < l:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	s = list(map(int, input().split()))
	if k > 0:
		s[n - 1] = s[n - 1] + k * (l - 1)
	ma = max(s)
	if ma == s[-1] and s.count(ma) == 1:
		print('Yes')
	else:
		print('No')


T = int(input())
for i in range(T):
	(npart, inc, dosecap) = map(int, input().split())
	sI = list(map(int, input().split()))
	if npart == 1:
		print('YES')
	else:
		a = sI[-1]
		b = max(sI[0:-1])
		if a > b:
			print('Yes')
		elif inc < 0:
			print('No')
		elif a + inc * (dosecap - 1) > b:
			print('Yes')
		else:
			print('No')


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	a = list(map(int, input().split()))
	s = a[n - 1]
	if k > 0:
		s += k * (l - 1)
	ans = True
	for i in range(n - 1):
		if a[i] >= s:
			ans = False
	if ans:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	Speed = list(map(int, input().split()))
	friend_speed = Speed[n - 1]
	if k > 0:
		friend_speed += k * (l - 1)
	answer = True
	for i in range(n - 1):
		if Speed[i] >= friend_speed:
			answer = False
	if answer:
		print('Yes')
	else:
		print('No')


def check(p, k, l):
	if k > 0:
		if p[-1] + k * (l - 1) > max(p):
			print('Yes')
		else:
			print('No')
	else:
		for i in range(len(p) - 1):
			if p[-1] < p[i]:
				print('No')
				return
		print('Yes')
for i in range(int(input())):
	k = list(map(int, input().split()))
	p = list(map(int, input().split()))
	check(p, k[1], k[2])