在佛罗里达男子的橘子园里,他又收到了一封由乌鸦寄来的垃圾邮件。当然,他会以最不方便的方式将其寄回。
一只乌鸦坐在数轴的 $$$0$$$ 位置。沿着数轴,在整数坐标 $$$a_1, a_2, \ldots, a_n$$$ 处有 $$$n$$$ 稻草人。这些稻草人被施了魔法,可以让它们以每秒 $$$1$$$ 单位的速度左右移动。
乌鸦害怕稻草人,并且希望与位于其或其之前的最近的稻草人保持至少 $$$k$$$ 的距离。为此,乌鸦使用其传送能力如下:
- 令 $$$x$$$ 为乌鸦的当前位置,并令 $$$y$$$ 为稻草人的最大位置,使得 $$$y \le x$$$。如果$$$x - y < k$$$,意味着稻草人太近,乌鸦将立即传送到位置$$$y + k$$$。
这种传送是即时且持续发生的。乌鸦会不断检查位于他或其左侧的稻草人,并在稻草人距离太近时进行传送(这可能会在非整数时间发生)。请注意,除了这种传送能力之外,乌鸦不会自行移动。
你的任务是确定让乌鸦传送到大于或等于 $$$\ell$$$ 的位置所需的最短时间,假设稻草人以最佳方式移动以允许乌鸦到达目标。为了方便起见,要求你输出乌鸦到达目标位置$$$\ell$$$所需最短时间的两倍。可以证明这个值永远是整数。
请注意,稻草人可以随时启动、停止或改变方向(可能在非整数时间)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n, k, \ell$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k \leq \ell \leq 10^8$$$)——分别是稻草人的数量、传送距离和乌鸦的目标位置。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq \ell$$$) — $$$n$$$ 稻草人的初始位置。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数,表示乌鸦传送到大于或等于 $$$\ell$$$ 的位置所需的最短时间的两倍。
示例
输入 #1
9 1 3 5 0 3 2 5 2 5 5 1 10 10 10 10 1 10 0 1 2 3 4 5 6 7 8 9 2 1 2 0 0 2 1 2 0 2 2 1 3 0 2 2 2 4 1 1 9 12 54 3 3 8 24 25 27 29 34 53
输出 #1
4 5 20 0 2 1 2 2 7
注意
在第一个测试用例中,由于位置 $$$0$$$ 处有稻草人,乌鸦立即传送到位置 $$$3$$$。然后,这个稻草人可能会移动到位置 $$$2$$$,导致乌鸦连续从位置 $$$3$$$ 移动到位置 $$$5$$$,在 $$$2$$$ 秒内完成行程。因此,输出为$$$4$$$。
在第二个测试用例中,稻草人$$$1$$$和稻草人$$$2$$$可以在$$$2$$$秒内分别移动到位置$$$0$$$和$$$3$$$,而稻草人$$$3$$$保持在位置$$$5$$$。由于稻草人 $$$1$$$,乌鸦传送到位置 $$$2$$$。然后,稻草人 $$$1$$$ 向右移动,而稻草人 $$$2$$$ 和稻草人 $$$3$$$ 向左移动 $$$0.5$$$ 秒。这会导致乌鸦不断地从位置 $$$2$$$ 移动到位置 $$$2.5$$$,因为稻草人 $$$1$$$ 从位置 $$$0$$$ 向右移动。半秒后,稻草人将位于 $$$0.5、2.5、4.5$$$ 位置。稻草人 $$$2$$$ 现在位于 $$$2.5$$$ 位置,导致乌鸦立即传送到位置 $$$4.5$$$,而位置 $$$4.5$$$ 的稻草人 $$$3$$$ 导致它立即传送到位置 $$$6.5$$$,这超过了 $$$\ell = 5$$$。因此,乌鸦只用了 $$$2.5$$$ 秒就完成了旅程,输出为 $$$5$$$。
可以证明,这些是两个测试用例的最小可能时间。