Zeus 正在分析战斗重播以了解对手的攻击模式。对手具有特殊能力:如果他们在 $$$z$$$ 时间内对目标进行三次攻击,他们的第三次攻击将成为强大的增强攻击。
为了击败对手,宙斯不应该让对手触发强化攻击。令 $$$Y = \{y_1, y_2, \ldots, y_m\}$$$ 为 $$$m$$$ 时间戳的多重集,其中每个 $$$y_i$$$ 代表对手攻击落地的时间。我们称 $$$Y$$$ 为 安全 如果对于每三个时间戳 $$$\{y_i, y_j, y_k\}$$$ 使得 $$$1 \le i \lt j \lt k \le m$$$,则认为 $$$\max(y_i, y_j, y_k) - \min(y_i, y_j, y_k) \gt z$$$,其中$$$z$$$ 是作为输入提供给您的时间范围的持续时间。
Zeus 有一个包含 $$$n$$$ 时间戳的日志,$$$x_1, x_2, \ldots, x_n$$$,代表对手攻击的时间。时间戳是 按非降序排序 。换句话说,$$$x_i \le x_{i+1}$$$ 对于所有$$$1 \le i \lt n$$$。
Zeus 有 $$$q$$$ 个兴趣区间,表示为两个整数 $$$1 \le l \le r \le n$$$。对于每个间隔,Zeus 希望找到 $$$[x_l, x_{l+1}, \ldots, x_r]$$$ 中他可以允许的最大攻击次数: 换句话说,Zeus 希望找到多重集 $$$\{x_l, x_{l+1}, \ldots, x_r\}$$$ 的最大大小子集,使得该子集为 安全.
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 20\,000$$$)。测试用例的描述如下。
第一行包含两个整数 $$$n$$$ 和 $$$z$$$ ($$$1 \le n \le 250\,000$$$, $$$1 \le z \le 10^9$$$)。
第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \le x_i \le 10^9$$$) — 对手攻击的时间戳。保证数组 $$$x$$$ 已排序,即 $$$x_i \le x_{i+1}$$$ 对于所有 $$$1 \le i \lt n$$$。
第三行包含一个整数 $$$q$$$ ($$$1 \le q \le 250\,000$$$)。
接下来的 $$$q$$$ 行每行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) - 区间的端点。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$250\,000$$$。
保证所有测试用例的 $$$q$$$ 总和不超过 $$$250\,000$$$。
输出
对于每个 $$$q$$$ 查询,打印一个整数 - 给定间隔内攻击时间戳安全子集的最大大小。
示例
输入复制
36 101 5 7 8 11 1261 61 52 61 42 53 66 11 1 1 3 3 323 31 612 154 5 15 24 27 32 36 39 40 46 48 48201 121 116 101 88 1211 122 93 87 87 104 89 129 102 121 53 124 83 77 1210 11
输出复制
3222221466242253222226452322
注意
在第一个测试用例的第一个查询中,我们考虑时间戳 $$$\{1, 5, 7, 8, 11, 12\}$$$ 和 $$$z=10$$$。子集 $$$\{1, 5, 12\}$$$ 是安全的,因为它唯一的三元组满足 $$$12 - 1 = 11 \gt 10$$$。不可能形成大小为 $$$4$$$ 的安全子集,因此该查询的答案是 $$$3$$$。
在第二个测试用例的第一个查询中,我们考虑时间戳 $$$\{1\}$$$ 和 $$$z=1$$$。整个集合 $$$\{1\}$$$ 是安全的,因为没有三元组。因此该查询的答案是$$$1$$$。
在第二个测试用例的第二个查询中,我们考虑时间戳 $$$\{1,1,1,3,3,3\}$$$ 和 $$$z=1$$$。
子集 $$$S = \{1,1,3,3\}$$$ 是安全的,因为:
- 对于三元组 $$$(i,j,k) = (1,2,3)$$$, $$$\max(1,1,3) - \min(1,1,3) = 2 \gt 1$$$。
- 对于三元组 $$$(i,j,k) = (1,2,4)$$$, $$$\max(1,1,3) - \min(1,1,3) = 2 \gt 1$$$。
- 对于三元组 $$$(i,j,k) = (1,3,4)$$$, $$$\max(1,3,3) - \min(1,3,3) = 2 \gt 1$$$。
- 对于三元组 $$$(i,j,k) = (2,3,4)$$$, $$$\max(1,3,3) - \min(1,3,3) = 2 \gt 1$$$。
不可能形成大小为 $$$5$$$ 的安全子集,因此此查询的答案是 $$$4$$$。