CF2207B.One Night At Freddy's

Five Nights at Freddy's 1 Song — The Living Tombstone

Let $n, m, \ell$ be positive integers. You have made the unfortunate decision to work as a night guard at Freddy Fazbear's Pizzeria, where there are $m$ animatronics numbered $1, \ldots, m$ waiting to jumpscare you.

The night consists of $\ell$ seconds, numbered $1, \ldots, \ell$. The $j$-th of the $m$ animatronics has a danger level $d_j$, and initially $d_1 = \ldots = d_m = 0$. Every second, the danger level of exactly one animatronic will increase by $1$, and throughout the night, you are able to observe all values of $d_j$ at the current time. For example, if $m = 2$, one possible list of danger levels after $5$ seconds is $[d_1, d_2] = [2, 3]$.

You are not defenseless, however. At each of the $n$ fixed times $a_i$ ($1 \leq a_1 \lt \ldots \lt a_n \leq \ell$), you can shine your flashlight on exactly one animatronic $j_i$ of your choice. This occurs immediately after the $a_i$-th second and sets its danger level back to zero, i.e. $d_{j_i} := 0$. Note that this choice is made independently for each flashlight use $a_i$. Continuing the example from before, if $a_1 = 5$ and you choose to flash the second animatronic at that time, the danger levels after $5$ seconds will be $[d_1, d_2] = [2, 0]$.

Let the overall danger be the maximum danger across all animatronics, i.e. $\max_{1 \leq j \leq m} d_j$. You will lose if the overall danger at the end of the night (after $\ell$ seconds) is greater than $x$. Find the minimum value of $x$ such that regardless of the actions of the animatronics, you can guarantee that overall danger will be less than or equal $x$.

《玩具熊的五夜后宫》主题曲 — The Living Tombstone

设 $n, m, \ell$ 为正整数。你不幸地决定在弗雷迪·法兹巴尔的披萨店担任夜间保安，店内共有 $m$ 个编号为 $1, \ldots, m$ 的机械玩偶，随时准备对你发起惊吓袭击。

一整晚共持续 $\ell$ 秒，秒数依次编号为 $1, \ldots, \ell$。第 $j$ 个（共 $m$ 个）机械玩偶具有危险等级 $d_j$；初始时所有危险等级均为零，即 $d_1 = \ldots = d_m = 0$。每一秒，恰好一个机械玩偶的危险等级增加 $1$；在整个夜晚中，你始终能实时观测到所有 $d_j$ 的当前值。例如，若 $m = 2$，经过 $5$ 秒后，一种可能的危险等级序列为 $[d_1, d_2] = [2, 3]$。

然而，你并非毫无防备。在固定的 $n$ 个时刻 $a_i$（满足 $1 \leq a_1 \lt \ldots \lt a_n \leq \ell$），你可以使用手电筒照射恰好一个你选定的机械玩偶 $j_i$。该操作发生在第 $a_i$ 秒结束之后立即执行，并将其危险等级重置为零，即令 $d_{j_i} := 0$。注意：每次手电筒使用（即每个 $a_i$）所选择的玩偶 $j_i$ 是独立决定的。延续前面的例子，若 $a_1 = 5$，且你在该时刻选择照射第二个玩偶，则经过 $5$ 秒后的危险等级变为 $[d_1, d_2] = [2, 0]$。

定义总体危险度为所有玩偶危险等级的最大值，即 $\max_{1 \leq j \leq m} d_j$。若在夜晚结束时（即 $\ell$ 秒后）总体危险度大于 $x$，你将失败。求最小的 $x$ 值，使得无论机械玩偶如何增加危险等级（即无论每秒哪个玩偶被选中增加危险等级），你总能通过合理选择每次手电筒照射的目标玩偶，保证最终总体危险度不超过 $x$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $m$, and $\ell$ ($1 \leq n, m, \ell \leq 2 \cdot 10^5, n \leq \ell, 1 \leq m \cdot \ell \leq 2 \cdot 10^5$) — the number of flashlight actions, animatronics, and the length of the night, respectively.

The next line contains $n$ integers $a_i$ ($1 \leq a_1 \lt \ldots \lt a_n \leq \ell$) — the times at which you get to shine your flashlight.

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $\ell$（$1 \leq n, m, \ell \leq 2 \cdot 10^5$，$n \leq \ell$，$1 \leq m \cdot \ell \leq 2 \cdot 10^5$），分别表示手电筒操作次数、机械玩偶数量以及夜晚总时长。

下一行包含 $n$ 个整数 $a_i$（$1 \leq a_1 \lt \ldots \lt a_n \leq \ell$），表示你可开启手电筒的时间点。

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

For each test case, output a single integer — the minimum $x$ such that you can guarantee that your final danger level is at most $x$.

对于每个测试用例，输出一个整数 —— 使得你能够保证最终危险等级不超过该值的最小 $x$。

In the first test case, there are $2$ animatronics and a night length of $10$, and you get to flash after the $10$-th second. We will show that $x = 5$ is always possible. After $10$ seconds, notice that one animatronic must have at least $5$ danger, and the other must have at most $5$ danger. So, we can flash the higher one and get a final danger level at most $5$. It can be shown that $5$ is the minimum possible value of $x$.

In the second test case, there is only one animatronic and a night length of $32$. Notice that in this case, the animatronic just increments its danger by $1$ each second. So, after the $25$-th second, we reset its danger to $0$. Seven more seconds pass before the night ends, so the final danger we get is always $7$.

In the third test case, it can be proven that the minimum possible value of $x$ is $19$.

在第一个测试用例中，有 $2$ 个机械玩偶，夜晚持续时间为 $10$ 秒，你可在第 $10$ 秒后进行一次闪光。我们将证明 $x = 5$ 总是可行的。经过 $10$ 秒后，注意到其中一个机械玩偶的危险值至少为 $5$，而另一个至多为 $5$。因此，我们可以对危险值较高的那个机械玩偶执行闪光操作，从而使得最终危险值至多为 $5$。可以证明，$5$ 是 $x$ 的最小可能取值。

在第二个测试用例中，仅有一个机械玩偶，夜晚持续时间为 $32$ 秒。注意在此情况下，该机械玩偶每秒将其危险值增加 $1$。因此，在第 $25$ 秒后，我们将其危险值重置为 $0$。此后夜晚还剩余 $7$ 秒，故最终得到的危险值恒为 $7$。

在第三个测试用例中，可以证明 $x$ 的最小可能取值为 $19$。