The only difference between easy and hard versions is on constraints. In this version constraints are higher. You can make hacks only if all versions of the problem are solved.

Koa the Koala is at the beach!

The beach consists (from left to right) of a shore, $n+1$ meters of sea and an island at $n+1$ meters from the shore.

She measured the depth of the sea at $1, 2, \dots, n$ meters from the shore and saved them in array $d$. $d_i$ denotes the depth of the sea at $i$ meters from the shore for $1 \le i \le n$.

Like any beach this one has tide, the intensity of the tide is measured by parameter $k$ and affects all depths from the beginning at time $t=0$ in the following way:

  For a total of $k$ seconds, each second, tide increases all depths by $1$.

  Then, for a total of $k$ seconds, each second, tide decreases all depths by $1$.

  This process repeats again and again (ie. depths increase for $k$ seconds then decrease for $k$ seconds and so on ...).

Formally, let's define $0$-indexed array $p = [0, 1, 2, \ldots, k - 2, k - 1, k, k - 1, k - 2, \ldots, 2, 1]$ of length $2k$. At time $t$ ($0 \le t$) depth at $i$ meters from the shore equals $d_i + p[t \bmod 2k]$ ($t \bmod 2k$ denotes the remainder of the division of $t$ by $2k$). Note that the changes occur instantaneously after each second, see the notes for better understanding. 

At time $t=0$ Koa is standing at the shore and wants to get to the island. Suppose that at some time $t$ ($0 \le t$) she is at $x$ ($0 \le x \le n$) meters from the shore:

  In one second Koa can swim $1$ meter further from the shore ($x$ changes to $x+1$) or not swim at all ($x$ stays the same), in both cases $t$ changes to $t+1$.

  As Koa is a bad swimmer, the depth of the sea at the point where she is can't exceed $l$ at integer points of time (or she will drown). More formally, if Koa is at $x$ ($1 \le x \le n$) meters from the shore at the moment $t$ (for some integer $t\ge 0$), the depth of the sea at this point  — $d_x + p[t \bmod 2k]$  — can't exceed $l$. In other words, $d_x + p[t \bmod 2k] \le l$ must hold always.

  Once Koa reaches the island at $n+1$ meters from the shore, she stops and can rest.

Note that while Koa swims tide doesn't have effect on her (ie. she can't drown while swimming). Note that Koa can choose to stay on the shore for as long as she needs and neither the shore or the island are affected by the tide (they are solid ground and she won't drown there). 

Koa wants to know whether she can go from the shore to the island. Help her!


-----Input-----

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

The first line of each test case contains three integers $n$, $k$ and $l$ ($1 \le n \le 3 \cdot 10^5; 1 \le k \le 10^9; 1 \le l \le 10^9$) — the number of meters of sea Koa measured and parameters $k$ and $l$.

The second line of each test case contains $n$ integers $d_1, d_2, \ldots, d_n$ ($0 \le d_i \le 10^9$)  — the depths of each meter of sea Koa measured.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.


-----Output-----

For each test case:

Print Yes if Koa can get from the shore to the island, and No otherwise.

You may print each letter in any case (upper or lower).


-----Example-----
Input
7
2 1 1
1 0
5 2 3
1 2 3 2 2
4 3 4
0 2 4 3
2 3 5
3 0
7 2 3
3 0 2 1 3 0 1
7 1 4
4 4 3 0 2 4 2
5 2 3
1 2 3 2 2

Output
Yes
No
Yes
Yes
Yes
No
No



-----Note-----

In the following $s$ denotes the shore, $i$ denotes the island, $x$ denotes distance from Koa to the shore, the underline denotes the position of Koa, and values in the array below denote current depths, affected by tide, at $1, 2, \dots, n$ meters from the shore.

In test case $1$ we have $n = 2, k = 1, l = 1, p = [ 0, 1 ]$.

Koa wants to go from shore (at $x = 0$) to the island (at $x = 3$). Let's describe a possible solution:

  Initially at $t = 0$ the beach looks like this: $[\underline{s}, 1, 0, i]$.  At $t = 0$ if Koa would decide to swim to $x = 1$, beach would look like: $[s, \underline{2}, 1, i]$ at $t = 1$, since $2 > 1$ she would drown. So Koa waits $1$ second instead and beach looks like $[\underline{s}, 2, 1, i]$ at $t = 1$.  At $t = 1$ Koa swims to $x = 1$, beach looks like $[s, \underline{1}, 0, i]$ at $t = 2$. Koa doesn't drown because $1 \le 1$.  At $t = 2$ Koa swims to $x = 2$, beach looks like $[s, 2, \underline{1}, i]$ at $t = 3$. Koa doesn't drown because $1 \le 1$.  At $t = 3$ Koa swims to $x = 3$, beach looks like $[s, 1, 0, \underline{i}]$ at $t = 4$.  At $t = 4$ Koa is at $x = 3$ and she made it! 

We can show that in test case $2$ Koa can't get to the island.

Difficulty: HARD
Tags: Greedy algorithms

Dynamic programming

Implementation

Constructive algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def solve():
	(n, k, l) = mints()
	x = 0
	for d in mints():
		z = l - d
		if z < 0:
			print('No')
			return
		if z >= k:
			x = 0
		elif x < k:
			x = max(x + 1, k - z)
		elif x >= k:
			x = x + 1
			if x - k > z:
				print('No')
				return
	print('Yes')
for i in range(mint()):
	solve()


import sys
input = sys.stdin.buffer.readline
T = int(input())
for _ in range(T):
	(n, k, l) = map(int, input().split())
	d = list(map(int, input().split()))
	if max(d) > l:
		print('No')
		continue
	(ls, cur) = ([], [])
	for (i, u) in enumerate(d):
		p = -1 if k <= l - u else l - u
		if p != -1:
			cur.append(p)
		else:
			ls.append(cur)
			cur = []
	ls.append(cur)
	ok = 1
	for cur in ls:
		if len(cur) <= 1:
			continue
		(s, dec) = (n, 1)
		for u in cur:
			if dec:
				s = min(s - 1, u)
				if s == 0:
					dec = 0
			else:
				s += 1
				if u < s:
					ok = 0
	print('Yes' if ok else 'No')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	d = list(map(int, input().split()))
	safe = [0]
	for i in range(n):
		if d[i] + k <= l:
			safe.append(i + 1)
	safe.append(n + 1)
	ok = True
	for i in range(1, len(safe)):
		tide = k
		down = True
		for j in range(safe[i - 1], safe[i] - 1):
			tide += -1 if down else 1
			if down:
				tide -= max(0, d[j] + tide - l)
			if tide < 0 or d[j] + tide > l:
				ok = False
				break
			if tide == 0:
				down = False
	if ok:
		print('Yes')
	else:
		print('No')


for t in range(int(input())):
	(n, k, l) = map(int, input().split())
	d = list(map(int, input().split()))
	a1 = 1 - k
	b1 = k
	for i in range(n):
		if d[i] > l:
			print('No')
			break
		a2 = max(d[i] - l, 1 - k)
		b2 = min(l - d[i], k)
		a = a1 + 1
		if b1 == k:
			a = 1 - k
		a2 = max(a2, a)
		if a2 > b2:
			print('No')
			break
		a1 = a2
		b1 = b2
	else:
		print('Yes')


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write('\n'.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
from fractions import Fraction
INF = float('inf')
mod = int(1000000000.0) + 7
for t in range(int(data())):
	(n, k, l) = mdata()
	d = mdata()
	flag = True
	m = k
	p = 0
	for j in range(0, n):
		if l - d[j] >= k:
			m = k - 1
			p = 0
		else:
			if d[j] + m > l and p == 1 or d[j] > l:
				flag = False
				break
			if p == 0:
				m = min(m - 1, l - d[j] - 1)
				if m == -1:
					p = 1
					m = 1
			else:
				m += 1
	if flag == True:
		out('Yes')
	else:
		out('No')


for t in range(int(input())):
	(n, k, l) = map(int, input().split())
	d = [False]
	d += list(map(int, input().split()))
	safe = [0]
	for i in range(n):
		if d[i] + k <= l:
			safe.append(i)
	safe.append(n + 1)
	n = len(safe)
	not_drown = True
	i = 1
	while i < n and not_drown:
		tide = k
		down = True
		start = safe[i - 1] + 1
		end = safe[i]
		for j in range(start, end):
			if down:
				tide -= 1
			else:
				tide += 1
			if down:
				tide -= max(0, d[j] + tide - l)
			if tide < 0 or d[j] + tide > l:
				not_drown = False
				break
			if tide == 0:
				down = False
		i += 1
	if not_drown:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	dd = list(map(int, input().split()))
	(t, curld, di) = (0, 0, False)
	for d in [-2 ** 30, *dd]:
		if d > l:
			break
		ld = l - d
		if d + k <= l:
			(curld, di) = (ld, False)
			continue
		if di:
			if ld >= curld + 1:
				curld += 1
			else:
				break
		else:
			curld = min(curld - 1, ld)
			if curld == 0:
				di = True
	else:
		print('Yes')
		continue
	print('No')


T = int(input())
for _ in range(T):
	(n, k, l) = map(int, input().split())
	d = list(map(int, input().split()))
	ranges = []
	t = -1000000000
	co = 0
	for i in range(n):
		ch = [max(t + 1, -l + d[i]), l - d[i]]
		t = max(-l + d[i], t + 1)
		if k <= l - d[i]:
			ch = [-1000000000, 102]
			t = -1000000000
		ranges.append(ch)
		if ranges[i][0] > ranges[i][1]:
			print('NO')
			co = 1
			break
	if co == 0:
		print('YES')


for h in range(int(input())):
	(n, k, l) = list(map(int, input().strip().split()))
	arr = list(map(int, input().strip().split()))
	dp = [0 for i in range(len(arr) + 1)]
	dp[0] = -1
	there = True
	for i in range(len(arr)):
		if arr[i] > l:
			there = False
			break
		elif arr[i] + k > l:
			dp[i + 1] = arr[i]
		else:
			dp[i + 1] = -1
	if there == False:
		print('No')
		continue
	pointer = 0
	for i in range(n + 1):
		if dp[i] == -1:
			if i == n:
				continue
			elif i < n:
				maxi = l - dp[i + 1]
				pointer = -maxi - 1
		else:
			pointer += 1
			if dp[i] + abs(pointer) > l:
				if pointer >= 0:
					there = False
					break
				else:
					pointer = -(l - dp[i])
	if there == False:
		print('No')
	else:
		print('Yes')


def main():
	t = int(input())
	for i in range(t):
		(n, k, l) = map(int, input().split())
		d = tuple(map(int, input().split()))
		output = 'Yes' if _can_get_to_finish(d, k, l) else 'No'
		print(output)

def _can_get_to_finish(depths, max_tide_height, max_height_can_swim):
	tide_heights_allowed = [max_height_can_swim - depth for depth in depths]
	get_tide_height = lambda time: _get_tide_height_by_time(time, max_tide_height)
	next_pos = 0
	last_checkpoint = None
	while True:
		prev_checkpoint = last_checkpoint
		next_time = -tide_heights_allowed[next_pos]
		while next_pos < len(tide_heights_allowed):
			allowed_height = tide_heights_allowed[next_pos]
			if allowed_height >= max_tide_height and next_pos != prev_checkpoint:
				last_checkpoint = next_pos
				next_pos += 1
				break
			if get_tide_height(next_time) > allowed_height:
				how_much_must_decrease = get_tide_height(next_time) - allowed_height
				if next_time + how_much_must_decrease > 0:
					return False
				next_time += how_much_must_decrease
			if get_tide_height(next_time) > allowed_height:
				if last_checkpoint is not None:
					next_pos = last_checkpoint
				else:
					next_pos = 0
				break
			next_pos += 1
			next_time += 1
		if next_pos >= len(tide_heights_allowed):
			return True
		if last_checkpoint == prev_checkpoint:
			return False

def _get_tide_height_by_time(time, max_tide_height):
	time %= 2 * max_tide_height
	if time < max_tide_height:
		result = time
	else:
		time_since_max = time - max_tide_height
		result = max_tide_height - time_since_max
	return result
main()


import sys
import collections

def input():
	return sys.stdin.readline().rstrip()

def split_input():
	return [int(i) for i in input().split()]
tests = int(input())
for _ in range(tests):
	(n, k, l) = split_input()
	d = split_input()
	newd = [l - i for i in d]
	if min(newd) < 0:
		print('No')
		continue
	kvalue = newd[0]
	dec = True
	ans = True
	i = 1
	while i < n:
		if newd[i] < 0:
			ans = False
			break
		if newd[i] >= k:
			if i < n - 1:
				kvalue = newd[i + 1]
				dec = True
				i += 2
				continue
		if kvalue == 0:
			dec = False
		if dec:
			if newd[i] < kvalue:
				kvalue = newd[i]
			else:
				kvalue -= 1
		elif newd[i] <= kvalue:
			ans = False
			break
		else:
			kvalue += 1
		i += 1
	if ans:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	depth = list(map(int, input().split()))
	fg = 1
	mn = -k
	mx = k
	for i in depth:
		if i > l:
			fg = 0
			break
		mx = min(l - i, k)
		if mx == k:
			mn = -k
		else:
			mn = max(mn + 1, -mx)
		if mn > mx:
			fg = 0
			break
	if fg:
		print('Yes')
	else:
		print('No')


import math

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

def ii():
	return int(input())

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

def si():
	return input().split()
t = ii()
for _ in range(t):
	(n, k, l) = mi()
	a = li()
	dp = [-1 for i in range(n)]
	ans = True
	rev = False
	if a[0] + k <= l:
		dp[0] = 'F'
	elif a[0] <= l:
		dp[0] = l - a[0]
		if dp[0] > 0:
			rev = True
		else:
			rev = False
	else:
		dp[0] = -1
	for i in range(1, n):
		if dp[i - 1] == -1 or a[i] > l:
			ans = False
			break
		if a[i] + k <= l:
			dp[i] = 'F'
		elif dp[i - 1] == 'F':
			dp[i] = l - a[i]
			if dp[i] > 0:
				rev = True
			else:
				rev = False
		elif rev:
			if l - a[i] <= dp[i - 1] - 1:
				dp[i] = l - a[i]
				if dp[i] > 0:
					rev = True
				else:
					rev = False
			else:
				dp[i] = dp[i - 1] - 1
				if dp[i] > 0:
					rev = True
				else:
					rev = False
		elif dp[i - 1] + 1 + a[i] <= l:
			dp[i] = dp[i - 1] + 1
			if dp[i] == k:
				rev = True
		else:
			ans = False
			break
	if ans and dp[n - 1] != -1:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	nkl = list(map(int, input().split()))
	n = nkl[0]
	k = nkl[1]
	l = nkl[2]
	d = list(map(int, input().split()))
	flag = 1
	count = 0
	leez = 0
	for i in range(n):
		if d[i] > l:
			flag = 0
			break
		else:
			if l - d[i] >= k:
				count = 0
				continue
			count += 1
			if count == 1:
				leez = l - d[i]
				continue
			leez = min(leez - 1, l - d[i])
			if leez >= 0:
				continue
			if -leez <= l - d[i]:
				continue
			else:
				flag = 0
				break
	if flag == 1:
		print('Yes')
	else:
		print('No')


import os, sys
from io import BytesIO, IOBase

def check(k, l, d, st, en):
	ad = k - 1
	for i in range(st + 1, en):
		if d[i] + abs(ad) <= l:
			ad -= 1
		else:
			if ad <= 0:
				return 0
			ad = l - d[i] - 1
	return 1

def solve(n, k, l, d):
	stops = [-1]
	for (ind, i) in enumerate(d):
		if i + k <= l:
			stops.append(ind)
		elif i > l:
			return 'NO'
	stops.append(n)
	for i in range(1, len(stops)):
		if not check(k, l, d, stops[i - 1], stops[i]):
			return 'NO'
	return 'YES'

def main():
	for _ in range(int(input())):
		(n, k, l) = map(int, input().split())
		d = list(map(int, input().split()))
		print(solve(n, k, l, d))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
while t > 0:
	(n, k, l) = map(int, input().split())
	a = list(map(int, input().split()))
	if max(a) > l:
		print('No')
	else:
		for i in range(n):
			if a[i] + k <= l:
				a[i] = -1
		ghata = -1
		p = 1
		y = 0
		for i in range(n):
			if a[i] == -1:
				ghata = -1
			elif ghata == -1:
				ghata = l - a[i]
				y = 0
				if ghata == 0:
					y = 1
					ghata += 1
				elif i != n - 1 and a[i + 1] != -1:
					ghata = ghata - 1
					if l < ghata + a[i + 1]:
						ghata = l - a[i + 1]
			elif a[i] + ghata > l:
				if y == 0:
					if l < ghata + a[i]:
						ghata = l - a[i]
					if ghata == 0:
						ghata += 1
						y = 1
					else:
						ghata = ghata - 1
				else:
					p = 0
					break
			elif y == 1 or ghata == 0:
				ghata = ghata + 1
				y = 1
			else:
				ghata = ghata - 1
		if p == 0:
			print('No')
		else:
			print('Yes')
	t = t - 1


import io
import os
from collections import Counter, defaultdict, deque

def solve(N, K, L, D):
	MOD = 2 * K
	if False:

		def getDepth(i, t):
			m = t % MOD
			tide = min(m, MOD - m)
			depth = D[i] + tide
			return depth
		for t in range(MOD):
			print(t, [getDepth(i, t) for i in range(N)])
	intervals = [(0, MOD - 1)]
	for (i, d) in enumerate(D):
		if d > L:
			return 'No'
		if d + K <= L:
			intervals = [(0, MOD - 1)]
			continue
		leaveIntervals = []
		for (s, e) in intervals:
			if e + 1 >= MOD:
				leaveIntervals.append((s + 1, MOD - 1))
				leaveIntervals = [(0, 0)] + leaveIntervals
			else:
				leaveIntervals.append((s + 1, e + 1))
		needed = L - d
		arriveIntervals = [(0, needed), (MOD - needed, MOD - 1)]
		newIntervals = []
		for leaveInterval in leaveIntervals:
			for arriveInterval in arriveIntervals:
				if leaveInterval[1] < arriveInterval[0] or arriveInterval[1] < leaveInterval[0]:
					continue
				newInterval = (max(leaveInterval[0], arriveInterval[0]), min(leaveInterval[1], arriveInterval[1]))
				if newIntervals and newIntervals[-1][-1] + 1 == newInterval[0]:
					old = newIntervals.pop()
					newIntervals.append((old[0], newInterval[1]))
				else:
					newIntervals.append(newInterval)
		if not newIntervals:
			return 'No'
		intervals = newIntervals
	return 'Yes'
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N, K, L) = [int(x) for x in input().split()]
	D = [int(x) for x in input().split()]
	ans = solve(N, K, L, D)
	print(ans)


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
from bisect import bisect_left as lower_bound, bisect_right as upper_bound

def so():
	return int(input())

def st():
	return input()

def mj():
	return map(int, input().strip().split(' '))

def msj():
	return map(str, input().strip().split(' '))

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

def lebe():
	return list(map(int, input()))

def dmain():
	sys.setrecursionlimit(1000000)
	threading.stack_size(1024000)
	thread = threading.Thread(target=main)
	thread.start()

def joro(L):
	return ''.join(map(str, L))

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def tr(n):
	return n * (n + 1) // 2

def iu():
	(n, p, q) = mj()
	L = le()
	(a, b) = (p, -p)
	g = 1
	for i in range(n):
		if q < L[i]:
			g = 0
			break
		a = min(q - L[i], p)
		if a != p:
			b = max(1 + b, -a)
		else:
			b = -q
		if a < b:
			g = 0
			break
	if g == 1:
		print('Yes')
	else:
		print('No')

def main():
	for i in range(so()):
		iu()
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def solve():
	(n, k, l) = map(int, input().split())
	dp = [[0, -1] for i in range(n)]
	lst = list(map(int, input().split()))
	dp[0][0] = l - lst[0]
	if dp[0][0] < 0:
		print('NO')
		return 0
	for i in range(1, n):
		if k + lst[i] <= l:
			dp[i] = [k, -1]
			continue
		if dp[i - 1][1] == 1:
			if dp[i - 1][0] == k:
				if k - 1 + lst[i] <= l:
					dp[i] = [k - 1, -1]
					continue
				else:
					print('NO')
					return 0
			if dp[i - 1][0] + 1 + lst[i] <= l:
				dp[i] = [dp[i - 1][0] + 1, 1]
			else:
				print('NO')
				return 0
		else:
			num = l - lst[i]
			if num < 0:
				print('NO')
				return 0
			if num < dp[i - 1][0]:
				dp[i][0] = num
			else:
				dp[i][0] = dp[i - 1][0] - 1
				if dp[i][0] == 0:
					dp[i][1] = 1
				elif dp[i][0] == -1:
					dp[i][0] = 1
					dp[i][1] = 1
				if dp[i][0] + lst[i] > l:
					print('NO')
					return 0
	print('YES')
for i in range(int(input())):
	solve()


production = True
import sys, math, collections

def input(input_format=0, multi=0):
	if multi > 0:
		return [input(input_format) for i in range(multi)]
	else:
		next_line = sys.stdin.readline()[:-1]
		if input_format >= 10:
			use_list = False
			input_format = int(str(input_format)[-1])
		else:
			use_list = True
		if input_format == 0:
			formatted_input = [next_line]
		elif input_format == 1:
			formatted_input = list(map(int, next_line.split()))
		elif input_format == 2:
			formatted_input = list(map(float, next_line.split()))
		elif input_format == 3:
			formatted_input = list(next_line)
		elif input_format == 4:
			formatted_input = list(map(int, list(next_line)))
		elif input_format == 5:
			formatted_input = next_line.split()
		else:
			formatted_input = [next_line]
		return formatted_input if use_list else formatted_input[0]

def out(output_line, output_format=0, newline=True):
	formatted_output = ''
	if output_format == 0:
		formatted_output = str(output_line)
	elif output_format == 1:
		formatted_output = ' '.join(map(str, output_line))
	elif output_format == 2:
		formatted_output = '\n'.join(map(str, output_line))
	elif output_format == 3:
		formatted_output = ''.join(map(str, output_line))
	print(formatted_output, end='\n' if newline else '')

def log(*args):
	if not production:
		print('$$$', end='')
		print(*args)
enu = enumerate
ter = lambda a, b, c: b if a else c
ceil = lambda a, b: -(-a // b)
flip = lambda a: a + 1 & 1

def mapl(iterable, format=0):
	if format == 0:
		return list(map(int, iterable))
	elif format == 1:
		return list(map(str, iterable))
	elif format == 2:
		return list(map(list, iterable))

def solve():
	(n, k, l) = input(1)
	d = input(1)
	log(k, l)
	log(d)
	f = [l - i for i in d]
	log(f)
	p = [(0, 2 * k - 1)]
	for i in f:
		(a, b) = p[-1]
		if i >= k:
			p.append((0, 2 * k - 1))
		else:
			fb = k + i
			fa = max(a + 1, k - i)
			log(i, fb, fa)
			if fb < fa:
				out('No')
				return
			p.append((fa, fb))
		log(p)
	else:
		out('Yes')
	log('')
	return
for i in range(input(11)):
	solve()


import sys
input = sys.stdin.readline
T = int(input())
for testcase in range(1, T + 1):
	(n, k, p) = map(int, input().split())
	D = list(map(int, input().split()))
	flag = True
	sta = 0
	end = 2 * k
	for d in D:
		if not flag:
			break
		if d > p:
			flag = False
		else:
			if d + k <= p:
				s = 0
				t = 2 * k
			else:
				s = k - (p - d)
				t = k + (p - d)
			if end + 1 < s or sta + 1 > t:
				flag = False
			else:
				if sta + 1 <= s <= end + 1:
					sta = s
					end = t
				else:
					sta = sta + 1
					end = t
				if end == 2 * k:
					sta = 0
	if flag:
		print('Yes')
	else:
		print('No')


t = int(input())
for you in range(t):
	l = input().split()
	n = int(l[0])
	k = int(l[1])
	l = int(l[2])
	lo = input().split()
	li = [int(i) for i in lo]
	arr = []
	poss = 1
	for i in li:
		if i > l:
			poss = 0
			break
		z = min(l - i, k)
		arr.append([-z, z])
	if poss == 0:
		print('no')
		continue
	for i in range(n):
		if i != 0:
			if arr[i][0] < curr and arr[i][0] != -k:
				arr[i][0] = curr
		curr = arr[i][0] + 1
		if arr[i][1] < arr[i][0]:
			poss = 0
			break
	if poss == 0:
		print('no')
	else:
		print('yes')


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

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

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

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]
for _ in range(II()):
	(n, k, l) = MI()
	s = t = -1
	ng = False
	for d in MI():
		if d > l:
			ng = True
			break
		mx = d + k
		if mx <= l:
			s = -1
			continue
		s += 1
		t += 1
		ns = mx - l
		nt = 2 * k - ns
		if s == 0:
			(s, t) = (ns, nt)
			continue
		if t < ns or nt < s:
			ng = True
			break
		s = max(s, ns)
		t = nt
	if ng:
		print('No')
	else:
		print('Yes')


for _ in range(int(input())):
	(n, k, l) = map(int, input().strip().split(' '))
	arr = list(map(int, input().strip().split(' ')))
	goods = []
	bad = False
	for (i, a) in enumerate(arr):
		if a + k <= l:
			goods.append(i)
		if a > l:
			bad = True
			break
	if bad:
		print('No')
		continue
	goods.append(n)
	prev = -1
	for g in goods:
		st = prev
		en = g
		if st + 1 == en:
			prev = g
			continue
		tk = k
		while st < en - 1 and tk > 0:
			st += 1
			tk -= 1
			plc = arr[st] + tk
			if plc > l:
				tk -= plc - l
			if tk < 0:
				bad = True
		if tk == 0:
			while st < en - 1:
				st += 1
				tk += 1
				plc = arr[st] + tk
				if plc > l:
					bad = True
					break
		if bad:
			break
		prev = g
	if bad:
		print('No')
	else:
		print('Yes')


t = int(input())
for i in range(t):
	(n, k, max_l) = map(int, input().split())
	lissht = list(map(int, input().split()))
	safe = [0]
	for ki in range(n):
		if lissht[ki] + k <= max_l:
			safe.append(ki + 1)
	safe.append(n + 1)
	ans = True
	for j in range(1, len(safe)):
		if ans == False:
			break
		if safe[j] - safe[j - 1] > 1:
			tide = k
			down = True
			for kij in range(safe[j - 1] + 1, safe[j]):
				if down == True:
					tide -= 1
				else:
					tide += 1
				if down == True:
					tide -= max(0, lissht[kij - 1] + tide - max_l)
				if lissht[kij - 1] + tide > max_l or tide < 0:
					ans = False
					break
				if tide == 0:
					down = False
	if ans:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k, l) = list(map(int, input().split()))
	d = list(map(int, input().split()))
	a = [0] * n
	failed = False
	for i in range(n):
		if d[i] + k <= l:
			a[i] = 2 * k
		elif d[i] > l:
			print('No')
			failed = True
			break
		else:
			a[i] = 1 + (l - d[i]) * 2
	if failed:
		continue
	steps = 0
	j = -1
	for i in range(n):
		if a[i] == 2 * k:
			steps = 0
			j = i
		else:
			steps += 1
			if steps >= (2 * k + a[i] + 1) // 2:
				failed = True
				break
			else:
				steps = max(steps, (2 * k - a[i] + 1) // 2)
	print('Yes' if not failed else 'No')


import math
import sys

def solve():
	(n, k, l) = map(int, input().split())
	a = list(map(int, input().split()))
	lt = -1
	for i in range(n):
		lt += 1
		if a[i] > l:
			print('No')
			return
		if l - a[i] >= k:
			lt = -1
			continue
		l1 = 2 * k - (l - a[i])
		r1 = 2 * k + (l - a[i])
		if lt == 0:
			lt = l1
			continue
		if lt > r1:
			print('No')
			return
		lt = max(lt, l1)
	print('Yes')
t = int(input())
for tt in range(t):
	solve()


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

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

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

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 0
	for w in arr:
		c += ceil(w / x)
	return c

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [(ch, len(list(g))) for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None
t = N()
for i in range(t):
	(n, k, l) = RLL()
	d = RLL()
	d = [l - x for x in d]
	if any((x < 0 for x in d)):
		ans = False
	else:
		res = []
		cur = []
		for x in d:
			if x >= k:
				if cur:
					res.append(cur)
					cur = []
			else:
				cur.append(x)
		if cur:
			res.append(cur)
		flag = True
		for a in res:
			last = 0
			for x in a:
				low = k - x
				upp = k + x
				cur = max(last + 1, low)
				if cur > upp:
					flag = False
					break
				last = cur
			if not flag:
				break
		ans = flag
	print('YES' if ans else 'NO')


t = int(input())
for _ in range(t):
	(n, k, l) = [int(x) for x in input().strip().split()]
	d = [int(x) for x in input().strip().split()]
	left = -k
	f = 0
	for i in range(n):
		if d[i] > l:
			print('No')
			f = 1
			break
		d[i] = min(l - d[i], k)
		if d[i] == k:
			left = -k
			continue
		if left >= d[i]:
			print('No')
			f = 1
			break
		left = max(-d[i], left + 1)
	if f == 0:
		print('Yes')


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nsmallest
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
from decimal import Decimal
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
for _ in range(int(data())):
	(n, k, L) = sp()
	d = l()
	(low, high) = (-k, k)
	result = True
	for i in range(n):
		if d[i] > L:
			result = False
			break
		high = min(L - d[i], k)
		if high == k:
			low = -k
		else:
			low = max(low + 1, -high)
		if low > high:
			result = False
			break
	out(('NO', 'YES')[result])


import sys, os.path
from collections import deque
from fractions import Fraction as f

def IO():
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	else:
		input = sys.stdin.readline
		print = sys.stdout.write

def nextInt():
	return int(input())

def nextTuple():
	return [int(a) for a in input().split()]

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

def nextLine():
	return input()

def nextStringArray():
	return list(input().split())
IO()
t = int(input())
for _ in range(t):
	(n, k, l) = [int(x) for x in input().split()]
	a = list(map(int, input().split()))
	flag = 0
	count = -1
	for i in range(n):
		if a[i] > l:
			flag = 1
			break
	for i in range(n):
		if a[i] + k > l:
			if count == -1:
				count = k + (a[i] + k) - l
				continue
			count += 1
			count = count % (2 * k)
			if count <= k:
				if a[i] + count > l:
					flag = 1
					break
			else:
				now = k + (a[i] + k) - l
				count = max(count, now)
		else:
			count = -1
	if flag == 1:
		print('No')
	else:
		print('Yes')


from sys import stdin, stdout

def koa_and_beach(n, k, l, d_a):
	sp_a = []
	for i in range(len(d_a)):
		if d_a[i] + k <= l:
			sp_a.append(i)
		if d_a[i] > l:
			return 'No'
	sp_a.append(n)
	pre = -1
	for i in sp_a:
		down = True
		ct = k
		for j in range(pre + 1, i):
			if down:
				ct -= 1
			else:
				ct += 1
			if d_a[j] + ct > l:
				if down:
					ct = l - d_a[j]
				else:
					return 'No'
			if ct == k:
				down = True
			elif ct == 0:
				down = False
		pre = i
	return 'Yes'
t = int(stdin.readline())
for _ in range(t):
	(n, k, l) = map(int, stdin.readline().split())
	d_a = list(map(int, stdin.readline().split()))
	res = koa_and_beach(n, k, l, d_a)
	stdout.write(str(res) + '\n')


import sys
inpy = [int(x) for x in sys.stdin.read().split()]
t = inpy[0]
index = 1
for _ in range(t):
	(n, k, l) = (inpy[index], inpy[index + 1], inpy[index + 2])
	index += 3
	d = inpy[index:index + n]
	index += n
	(x, m) = (k, True)
	flag = True
	for i in range(n):
		diff = l - d[i]
		if diff < 0:
			flag = False
			break
		if diff >= k:
			x = k
			m = True
		elif m:
			x = min(x - 1, diff)
			if x == 0:
				m = False
		else:
			x = x + 1
			if x > diff:
				flag = False
				break
	if flag:
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	(n, k, l) = [int(x) for x in input().split()]
	d = [int(x) for x in input().split()]
	for i in range(n):
		d[i] -= l
	safeSpots = set()
	ok = True
	for i in range(n):
		if d[i] + k <= 0:
			safeSpots.add(i)
		if d[i] > 0:
			print('No')
			ok = False
			break
	if ok == False:
		continue

	def getAdditionalDepth(t):
		t2 = t % (2 * k)
		if t2 > k:
			t2 = 2 * k - t2
		return t2
	ok = True
	t = k
	if d[0] + getAdditionalDepth(t) > 0:
		t += d[0] + getAdditionalDepth(t)
	d.append(-float('inf'))
	for i in range(n):
		if t >= 2 * k:
			t -= 2 * k
		if i + 1 in safeSpots:
			t = k
			continue
		nextDepth = d[i + 1] + getAdditionalDepth(t + 1)
		if nextDepth <= 0:
			t += 1
			continue
		else:
			if t + 1 <= k:
				ok = False
				break
			earliestTime = t + nextDepth
			t = earliestTime + 1
	if ok:
		print('Yes')
	else:
		print('No')


def main():
	t = int(input())
	for i in range(t):
		(n, k, l) = map(int, input().split())
		d = tuple(map(int, input().split()))
		output = 'Yes' if _can_get_to_finish(d, k, l) else 'No'
		print(output)

def _can_get_to_finish(depths, max_tide_height, max_height_can_swim):
	tide_heights_allowed = [max_height_can_swim - depth for depth in depths]
	if any((allowed_height < 0 for allowed_height in tide_heights_allowed)):
		return False
	get_tide_height = lambda time: _get_tide_height_by_time(time, max_tide_height)
	next_pos = 0
	curr_checkpoint = None
	while True:
		next_time = -tide_heights_allowed[next_pos]
		while True:
			max_allowed_height = tide_heights_allowed[next_pos]
			if max_allowed_height >= max_tide_height:
				curr_checkpoint = next_pos
				next_pos += 1
				if next_pos >= len(tide_heights_allowed):
					return True
				break
			if get_tide_height(next_time) > max_allowed_height:
				how_much_must_wait = get_tide_height(next_time) - max_allowed_height
				if next_time + how_much_must_wait > 0:
					return False
				next_time += how_much_must_wait
			next_pos += 1
			next_time += 1
			if next_pos >= len(tide_heights_allowed):
				return True

def _get_tide_height_by_time(time, max_tide_height):
	time %= 2 * max_tide_height
	if time < max_tide_height:
		result = time
	else:
		time_since_max = time - max_tide_height
		result = max_tide_height - time_since_max
	return result
main()


for i in range(int(input())):
	(n, k, l) = map(int, input().split())
	inp = list(map(int, input().split()))
	inp = [l - x for x in inp]
	a = []
	curr = []
	if min(inp) >= 0:
		ans = 'Yes'
	else:
		ans = 'No'
	for x in inp:
		if x >= k:
			if len(curr) > 1:
				a.append(curr)
			curr = []
		else:
			curr.append(x)
	a.append(curr)
	for ls in a:
		td = k
		dsc = True
		for x in ls:
			if dsc:
				td = min(td - 1, x)
				if td == 0:
					dsc = False
			else:
				td += 1
				if td > x:
					ans = 'No'
	print(ans)


import sys
import math
from collections import defaultdict
import heapq
t = int(sys.stdin.readline())
for _ in range(t):
	(n, k, l) = map(int, sys.stdin.readline().split())
	d = list(map(int, sys.stdin.readline().split()))
	p = []
	z = True
	dic = defaultdict(list)
	arr = []
	safe = [False for x in range(n)]
	for i in range(n):
		arr.append(l - d[i])
		if l - d[i] >= k:
			safe[i] = True
		if arr[i] < 0:
			z = False
	if z == False:
		print('No')
		continue
	m = False
	t = k
	z = True
	for i in range(n):
		if safe[i]:
			t = k
			m = False
			continue
		if arr[i] >= t:
			if not m:
				t -= 1
				if t == 0:
					m = True
			else:
				t += 1
				if t == k + 1:
					m = False
					t = k
		elif not m:
			t = arr[i] - 1
			if t == 0:
				m = True
			if t < 0:
				t = 1
				m = True
		else:
			z = False
			break
	if not z:
		print('No')
		continue
	print('Yes')


def solve(arr, n, k, l):
	min_t = 0
	for v in arr:
		if v > l:
			return False
		if k + v <= l:
			min_t = 0
		else:
			new_min_t = k - l + v
			min_t = max(min_t + 1, new_min_t)
		if min_t > k + l - v:
			return False
	return True
for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	(*arr,) = map(int, input().split())
	print('YES' if solve(arr, n, k, l) else 'NO')


t = int(input())
for s in range(t):
	(n, k, l) = map(int, input().split())
	a = list(map(int, input().split()))
	(mini, maxi) = ([], [])
	flag = 0
	for i in range(n):
		if a[i] <= l:
			if a[i] + k <= l:
				mini.append(-999999999)
				maxi.append(999999999)
			else:
				mini.append(a[i] - l)
				maxi.append(l - a[i])
		else:
			flag = 1
			break
	if flag == 1:
		print('No')
		continue
	i = 0
	while i < n - 1:
		if mini[i + 1] == -999999999:
			i += 1
		elif mini[i] < 0:
			if mini[i] + 1 > mini[i + 1]:
				mini[i + 1] = mini[i] + 1
		else:
			mini[i + 1] = mini[i] + 1
			if mini[i + 1] > maxi[i + 1]:
				flag = 2
				break
		i += 1
	if flag == 2:
		print('No')
	else:
		print('Yes')


def main():
	t = int(input())
	for i in range(t):
		(n, k, l) = map(int, input().split())
		d = tuple(map(int, input().split()))
		output = 'Yes' if _can_get_to_finish(d, k, l) else 'No'
		print(output)

def _can_get_to_finish(depths, max_tide_height, max_height_can_swim):
	tide_heights_allowed = [max_height_can_swim - depth for depth in depths]
	if any((allowed_height < 0 for allowed_height in tide_heights_allowed)):
		return False
	sea_size = len(tide_heights_allowed)

	def is_checkpoint(pos):
		return tide_heights_allowed[pos] >= max_tide_height
	get_tide_height = lambda time: _get_tide_height_by_time(time, max_tide_height)
	next_pos = 0
	curr_checkpoint = -1
	while next_pos < sea_size:
		time_of_next_pos = -tide_heights_allowed[next_pos]
		while next_pos < sea_size and (not is_checkpoint(next_pos)):
			max_allowed_height = tide_heights_allowed[next_pos]
			if get_tide_height(time_of_next_pos) > max_allowed_height:
				how_much_must_wait = get_tide_height(time_of_next_pos) - max_allowed_height
				if time_of_next_pos + how_much_must_wait > 0:
					return False
				time_of_next_pos += how_much_must_wait
			next_pos += 1
			time_of_next_pos += 1
		while next_pos < sea_size and is_checkpoint(next_pos):
			curr_checkpoint = next_pos
			next_pos += 1
	return True

def _get_tide_height_by_time(time, max_tide_height):
	time %= 2 * max_tide_height
	if time < max_tide_height:
		result = time
	else:
		time_since_max = time - max_tide_height
		result = max_tide_height - time_since_max
	return result
main()


t = int(input())
for _ in range(t):
	(n, k, l) = list(map(int, input().split()))
	d = list(map(int, input().split()))
	last = 0
	depths = []
	for i in range(len(d)):
		if d[i] <= l - k:
			if len(d[last:i]) > 0:
				depths.append(d[last:i])
			last = i + 1
	if len(d[last:]) > 0:
		depths.append(d[last:])
	cross = True
	for a in depths:
		ok = True
		tide = k
		down = True
		for i in range(len(a)):
			if a[i] > l:
				ok = False
				break
			elif down:
				if tide > l - a[i]:
					tide = l - a[i]
				else:
					tide -= 1
				if tide == 0:
					down = False
			elif a[i] + tide + 1 > l:
				ok = False
				break
			else:
				tide += 1
		if not ok:
			cross = False
			break
	if cross:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	d = list(map(int, input().split()))
	seg = []
	for i in range(n):
		if l - d[i] < 0:
			print('No')
			break
		seg.append([-min(l - d[i], k), min(l - d[i], k)])
	else:
		now = seg[0][0]
		for i in range(1, n):
			if seg[i] == [-k, k]:
				now = seg[i][0]
			else:
				now += 1
				if now < seg[i][0]:
					now = seg[i][0]
				elif now > seg[i][1]:
					print('No')
					break
		else:
			print('Yes')


t = int(input())
for _ in range(t):
	(n, k, l) = map(int, input().split())
	arr = list(map(int, input().split()))
	maxi = k
	mini = -k
	flag = True
	for i in range(n):
		if arr[i] > l:
			flag = False
			break
		maxi = min(l - arr[i], k)
		if maxi == k:
			mini = -k
		else:
			mini = max(mini + 1, -maxi)
		if mini > maxi:
			flag = False
			break
	if flag:
		print('Yes')
	else:
		print('No')


import sys
input = sys.stdin.readline

def riverCross(arr, n, k, l):
	to = None
	jump = 0
	reverse = -1
	ans = None
	if n == 1:
		if arr[0] > l:
			ans = 'No'
			return 'No'
		else:
			ans = 'Yes'
			return 'Yes'
	else:
		for i in range(len(arr) - 1):
			minimum = arr[i]
			maximum = arr[i] + k
			if maximum <= l:
				nextMax = arr[i + 1] + k
				if arr[i + 1] > l:
					ans = 'No'
					return 'No'
				elif nextMax <= l:
					jump += 1
					to = arr[i + 1] + k
				else:
					to = nextMax
					if to > l:
						to = l
						if to == arr[i + 1]:
							reverse = 1
						elif to == arr[i + 1] + k:
							reverse = -1
					jump += 1
			elif minimum > l:
				ans = 'No'
				return 'No'
			else:
				nextMax = arr[i + 1] + k
				if arr[i + 1] > l:
					ans = 'No'
					return 'No'
				elif nextMax <= l:
					to = arr[i + 1] + k
					if to == arr[i + 1]:
						reverse = 1
					elif to == arr[i + 1] + k:
						reverse = -1
					jump += 1
				else:
					if to == None:
						to = arr[i] + k - 1
						if to > l:
							to = l
					if reverse == -1:
						gapTime = (to - arr[i]) * 2 + 1
					else:
						gapTime = arr[i] + k - to
					to = arr[i + 1] + k - maximum + to
					if to == arr[i + 1]:
						reverse = 1
					elif to == arr[i + 1] + k:
						reverse = -1
					if reverse == -1:
						to -= 1
					else:
						to += 1
					if to > l:
						if reverse == -1:
							gapTime -= to - l
							if gapTime <= 0:
								ans = 'No'
								return 'No'
							to = l
						elif reverse == 1:
							gapTime -= arr[i + 1] + k - to + arr[i + 1] + k - l
							if gapTime <= 0:
								ans = 'No'
								return 'No'
							to = l
						if to == arr[i + 1]:
							reverse = 1
						elif to == arr[i + 1] + k:
							reverse = -1
					jump += 1
			if to == arr[i + 1]:
				reverse = 1
			elif to == arr[i + 1] + k:
				reverse = -1
			if jump == n - 1:
				if to <= l:
					return 'Yes'
				else:
					return 'No'

def solution():
	values = list(map(lambda x: int(x), input().split()))
	n = values[0]
	k = values[1]
	l = values[2]
	arr = list(map(lambda x: int(x), input().split()))
	print(riverCross(arr, n, k, l))
t = int(input())
for i in range(0, t):
	solution()


ans = []
for _ in range(int(input())):
	(n, k, L) = map(int, input().split())
	u = list(map(int, input().split()))
	x = 0
	for d in u:
		z = L - d
		if z < 0:
			ans.append('No')
			break
		if z >= k:
			x = 0
		elif x < k:
			x = max(x + 1, k - z)
		elif x >= k:
			x += 1
			if x - k > z:
				ans.append('No')
				break
	else:
		ans.append('Yes')
print('\n'.join(ans))


from sys import stdin, stdout

def arrinp():
	return [*map(int, stdin.readline().split(' '))]

def mulinp():
	return map(int, stdin.readline().split(' '))

def intinp():
	return int(stdin.readline())

def inp():
	return stdin.readline()

def solution():
	(n, k, l) = mulinp()
	d = [0] + arrinp()
	if max(d) > l:
		print('No')
		return
	impflag = 0
	free = [0] * (n + 2)
	for i in range(n + 1):
		depth = d[i]
		if depth + k <= l:
			free[i] = 1
	free[0] = 1
	free[n + 1] = 1
	t = 0
	for i in range(n + 2):
		if free[i]:
			t = 0
		else:
			t += 1
			if t > k:
				if t - k + d[i] > l:
					impflag = 1
					break
			elif k - t + d[i] > l:
				t += k - t + d[i] - l
	if impflag == 0:
		print('Yes')
	else:
		print('No')
testcases = 1
testcases = intinp()
for _ in range(testcases):
	solution()


import sys
input = sys.stdin.buffer.readline

def getAdditionalDepth(t):
	t2 = t % (2 * k)
	if t2 > k:
		t2 = 2 * k - t2
	return t2
t = int(input())
for _ in range(t):
	(n, k, l) = [int(x) for x in input().split()]
	d = [int(x) for x in input().split()]
	ok = True
	for i in range(n):
		d[i] -= l
		if d[i] > 0:
			print('No')
			ok = False
			break
	if ok == False:
		continue
	t = k
	if d[0] + getAdditionalDepth(t) > 0:
		t += d[0] + getAdditionalDepth(t)
	for i in range(n - 1):
		if t >= 2 * k:
			t -= 2 * k
		if d[i + 1] + k <= 0:
			t = k
			continue
		nextDepth = d[i + 1] + getAdditionalDepth(t + 1)
		if nextDepth <= 0:
			t += 1
		elif t < k:
			ok = False
			break
		else:
			t += nextDepth + 1
	if ok:
		print('Yes')
	else:
		print('No')


f = lambda : map(int, input().split())
(t,) = f()
for _ in [0] * t:
	(n, k, l) = f()
	s = [*f()]
	a = 0
	z = k - 1
	for i in s:
		if i + k <= l:
			z = k - 1
		elif z >= 0 and l >= i:
			z = min(z, l - i) - 1
		elif l < i or abs(z) > l - i:
			a = 1
		else:
			z -= 1
	print('YNeos'[a::2])


import sys
import math
input = sys.stdin.readline
T = int(input())
for t in range(T):
	(N, k, limit) = map(int, input().split(' '))
	A = list(map(int, input().split(' ')))
	lowest_tide = k
	tide = k
	time = 0
	can = True
	for i in range(N):
		if A[i] > limit:
			can = False
			break
		if A[i] + k <= limit:
			time = 0
			tide = k
		else:
			if time < k:
				min_step = max(A[i] + tide - limit, 1)
				tide -= min_step
				time += min_step
			else:
				tide += 1
				time += 1
			if A[i] + tide > limit or tide < 0:
				can = False
				break
	print('Yes' if can else 'No')


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.buffer.readline
	for _ in range(int(input())):
		(N, K, L) = map(int, input().split())
		A = list(map(int, input().split()))
		A.append(-K)
		if max(A) > L:
			print('No')
			continue
		ok = 1
		k = -K - 1
		for a in A:
			k += 1
			if k < 0:
				if a + K <= L:
					k = -K - 1
				if a - k > L:
					k = -(L - a)
			elif a + k > L:
				ok = 0
				break
			elif a + K <= L:
				k = -K - 1
		if ok:
			print('Yes')
		else:
			print('No')
main()


import sys
import os, io
input = sys.stdin.readline

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

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

def print_list(l):
	print(' '.join(map(str, l)))
N = int(input())
for _ in range(N):
	(n, k, l) = read_list()
	d = read_list()
	if max(d) > l:
		print('No')
	else:
		flag = True
		tt = 2 * k
		now = tt
		for i in range(n):
			if d[i] + k <= l:
				tmp = tt
			else:
				tm = d[i] + k - l
				tmp = [tm, 2 * k - tm]
			if tmp == tt:
				now = tt
			elif now == tt:
				now = tmp
			else:
				now = [max(now[0] + 1, tmp[0]), min(now[1] + 1, tmp[1])]
				if now[0] > now[1]:
					flag = False
					break
		if flag:
			print('Yes')
		else:
			print('No')


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
import copy

def gift():
	for _ in range(t):
		(n, k, l) = list(map(int, input().split()))
		arry = list(map(int, input().split()))
		prevdis = float('inf')
		increase = False
		for val in arry:
			if val > l:
				break
			dis = l - val
			if dis >= k:
				prevdis = dis
				increase = False
				continue
			if increase:
				if dis >= prevdis + 1:
					prevdis += 1
				else:
					break
			else:
				prevdis = min(prevdis - 1, dis)
				if prevdis == 0:
					increase = True
		else:
			yield 'Yes'
			continue
		yield 'No'
t = int(input())
ans = gift()
print(*ans, sep='\n')


import time, math as mt, bisect, sys
from sys import stdin, stdout
from collections import deque
from fractions import Fraction
from collections import Counter
from collections import OrderedDict
pi = 3.141592653589793

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

def IO():
	return stdin.readline()

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

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

def P(x):
	return stdout.write(str(x) + '\n')

def PI(x, y):
	return stdout.write(str(x) + ' ' + str(y) + '\n')

def lcm(a, b):
	return a * b // gcd(a, b)

def gcd(a, b):
	if a == 0:
		return b
	elif b == 0:
		return a
	if a > b:
		return gcd(a % b, b)
	else:
		return gcd(a, b % a)

def readTree():
	v = int(input())
	adj = [set() for i in range(v + 1)]
	for i in range(v - 1):
		(u1, u2) = In()
		adj[u1].add(u2)
		adj[u2].add(u1)
	return (adj, v)

def bfs(adj, v):
	visited = [False] * (v + 1)
	q = deque()
	while q:
		pass

def sieve():
	li = [True] * 1000001
	(li[0], li[1]) = (False, False)
	for i in range(2, len(li), 1):
		if li[i] == True:
			for j in range(i * i, len(li), i):
				li[j] = False
	prime = []
	for i in range(1000001):
		if li[i] == True:
			prime.append(i)
	return prime

def setBit(n):
	count = 0
	while n != 0:
		n = n & n - 1
		count += 1
	return count
mx = 10 ** 7
spf = [mx] * (mx + 1)

def SPF():
	spf[1] = 1
	for i in range(2, mx + 1):
		if spf[i] == mx:
			spf[i] = i
			for j in range(i * i, mx + 1, i):
				if i < spf[j]:
					spf[j] = i
	return
mod = 10 ** 9 + 7

def solve():
	(n, k, l) = IP()
	d = L()
	for ele in d:
		if ele > l:
			print('NO')
			return
	time = [[0, 0] for i in range(n)]
	for i in range(n):
		ele = d[i]
		time[i][0] = -1 * min(l - ele, k)
		time[i][1] = min(l - ele, k)
	for i in range(1, n):
		if time[i][0] != -1 * k:
			if time[i][0] <= time[i - 1][0]:
				time[i][0] = time[i - 1][0] + 1
				if time[i][0] > time[i][1]:
					print('NO')
					return
	else:
		print('YES')
		return
t = II()
for i in range(t):
	solve()


t = int(input())
for i in range(t):
	(n, k, l) = map(int, input().split())
	b = list(map(int, input().split()))
	f = 0
	if b[0] > l:
		f = 1
	j = 1
	pr = 0
	m = 1
	while j < n:
		if b[j] + k <= l:
			m = 1
			pass
		else:
			if b[j] > l:
				f = 1
				break
			if b[j - 1] + k <= l:
				pr = 0
				m = 1
			else:
				if pr == 0:
					q = l + b[j] - b[j - 1] - 1
					s = 0
					if q > l:
						q = l
						s = 1
					elif q >= b[j]:
						s = 1
					if s == 0:
						q = l + b[j] - b[j - 1] + 1
						if q < b[j]:
							q = b[j]
							s = 1
						elif q <= l:
							s = 1
						m = 0
					if s == 0:
						f = 1
						break
					curr = q
					pr = 1
					if m == 1 and curr == b[j]:
						m = 0
				else:
					s = 0
					if m == 0:
						q = curr + b[j] - b[j - 1] + 1
						if q < b[j]:
							s = 1
							q = b[j]
						elif q <= l:
							s = 1
					else:
						q = curr + b[j] - b[j - 1] - 1
						if q > l:
							q = l
							s = 1
						elif q >= b[j]:
							s = 1
					if s == 0:
						f = 1
						break
					curr = q
				if m == 1 and curr == b[j]:
					m = 0
		j += 1
	if f == 0:
		print('Yes')
	else:
		print('No')


from sys import stdin, stdout
import math
t = int(stdin.readline())
for _ in range(t):
	(n, k, l) = map(int, stdin.readline().split())
	d = [-k] + list(map(int, stdin.readline().split())) + [-k]
	t = 0
	for i in range(n + 1):
		x = d[i]
		cur = t % (2 * k)
		curth = cur if cur <= k else k - (cur - k)
		if x > l or x + curth > l:
			break
		nx = d[i + 1]
		best = 2 * k - (l - nx)
		if best < k:
			best = k
		if cur < k:
			if best == k:
				if x + k - 1 > l:
					t += 1
					continue
			elif x + k > l:
				t += 1
				continue
		elif best <= cur:
			if x + k > l:
				t += 1
				continue
		t = best
		t %= 2 * k
	else:
		print('YES')
		continue
	print('NO')