CF1384B2.Koa and the Beach (Hard Version)

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!

简单版本与困难版本的唯一区别在于约束条件。在本版本中，约束条件更为严格。仅当该题的所有版本均已被解决时，才允许进行 Hack。

考拉小 koa 正在海滩上！

海滩由左至右依次为：海岸线、长度为 $n+1$ 米的海域，以及位于距海岸线 $n+1$ 米处的一座岛屿。

她测量了距海岸线 $1, 2, \dots, n$ 米处的海水深度，并将结果保存在数组 $d$ 中。其中 $d_i$ 表示距海岸线 $i$ 米处（$1 \le i \le n$）的海水深度。

和所有海滩一样，此处也有潮汐；潮汐强度由参数 $k$ 刻画，并从时刻 $t=0$ 开始以如下方式影响所有水深：

• 在总共 $k$ 秒内，每秒潮汐使所有水深增加 $1$；
• 接着，在总共 $k$ 秒内，每秒潮汐使所有水深减少 $1$；
• 此过程不断重复（即：水深先持续 $k$ 秒上升，再持续 $k$ 秒下降，如此往复……）。

形式化地，定义一个长度为 $2k$ 的、下标从 $0$ 开始的数组 $p = [0, 1, 2, \ldots, k - 2, k - 1, k, k - 1, k - 2, \ldots, 2, 1]$。在时刻 $t$（$t \ge 0$），距海岸线 $i$ 米处的水深为 $d_i + p[t \bmod 2k]$（其中 $t \bmod 2k$ 表示 $t$ 除以 $2k$ 的余数）。注意：水深变化在每秒结束时瞬时发生，详见样例说明以加深理解。

在时刻 $t = 0$，koa 站在海岸线上，希望抵达岛屿。假设在某个时刻 $t$（$t \ge 0$），她位于距海岸线 $x$（$0 \le x \le n$）米处：

• 每秒，koa 可向前游进 $1$ 米（即 $x$ 变为 $x+1$），或选择静止不动（$x$ 保持不变）；无论哪种情况，时间 $t$ 均变为 $t+1$；
• 由于 koa 是一名蹩脚的游泳者，她在任意整数时刻所处位置的水深不能超过 $l$（否则她将溺水）。更准确地说：若在某个整数时刻 $t \ge 0$，koa 位于距海岸线 $x$（$1 \le x \le n$）米处，则该处水深 $d_x + p[t \bmod 2k]$ 不得超过 $l$。换言之，恒须满足 $d_x + p[t \bmod 2k] \le l$；
• 一旦 koa 抵达位于距海岸线 $n+1$ 米处的岛屿，她便停止前进并可以休息。

注意：koa 在游泳过程中不受潮汐影响（即游泳途中不会溺水）。此外，koa 可在海岸线上停留任意长时间；且海岸线与岛屿本身不受潮汐影响（它们是坚实的陆地，koa 在其上绝不会溺水）。

koa 想知道她是否能从海岸线成功抵达岛屿。请帮帮她！

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$.

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$k$ 和 $l$（$1 \le n \le 3 \cdot 10^5$；$1 \le k \le 10^9$；$1 \le l \le 10^9$），分别表示 Koa 测量的海水长度（单位：米）以及参数 $k$ 和 $l$。

每个测试用例的第二行包含 $n$ 个整数 $d_1, d_2, \ldots, d_n$（$0 \le d_i \le 10^9$），表示 Koa 测量的每米海水的深度。

保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

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).

对于每个测试用例：

如果 Koa 能够从岸边到达小岛，则输出 Yes；否则输出 No。

你可以以任意大小写（大写或小写）输出每个字母。

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 \gt 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.

以下符号中，$s$ 表示海岸线，$i$ 表示岛屿，$x$ 表示 Koa 距离海岸线的距离，下划线表示 Koa 当前所在位置，下方数组中的数值表示在距海岸线 $1, 2, \dots, n$ 米处的当前水深（受潮汐影响）。

在测试用例 $1$ 中，我们有 $n = 2,\ k = 1,\ l = 1,\ p = [ 0,\ 1 ]$。

Koa 想要从海岸线（位于 $x = 0$）出发，到达岛屿（位于 $x = 3$）。下面描述一种可行方案：

• 初始时刻 $t = 0$，海滩状态为：$[\underline{s},\ 1,\ 0,\ i]$。
• 在 $t = 0$ 时，若 Koa 决定游向 $x = 1$，则在 $t = 1$ 时海滩状态将变为：$[s,\ \underline{2},\ 1,\ i]$；由于 $2 > 1$，她将溺水。因此 Koa 改为等待 $1$ 秒，使得 $t = 1$ 时海滩状态为：$[\underline{s},\ 2,\ 1,\ i]$。
• 在 $t = 1$ 时，Koa 游向 $x = 1$，则在 $t = 2$ 时海滩状态为：$[s,\ \underline{1},\ 0,\ i]$；由于 $1 \le 1$，她未溺水。
• 在 $t = 2$ 时，Koa 游向 $x = 2$，则在 $t = 3$ 时海滩状态为：$[s,\ 2,\ \underline{1},\ i]$；由于 $1 \le 1$，她未溺水。
• 在 $t = 3$ 时，Koa 游向 $x = 3$，则在 $t = 4$ 时海滩状态为：$[s,\ 1,\ 0,\ \underline{i}]$。
• 在 $t = 4$ 时，Koa 已抵达 $x = 3$，成功登岛！

我们可以证明：在测试用例 $2$ 中，Koa 无法抵达岛屿。