小A惊魂夜

题目描述

给定正整数 n, m, l。

你在小A披萨店值夜班，有 m 个机械玩偶（编号 1...m）可能对你造成惊吓。夜晚持续 l 秒，编号 1...l。

第 $j$ 个玩偶有危险值 $d_j$，初始时全部为 0。每一秒钟，恰好有一个玩偶的危险值增加 1。因此在任意时刻，你都能看到当前所有 $d_j$ 的值。

你有手电筒可以反制。在固定的 n 个时刻 $a_i$（$1 \leq a_1 < ... < a_n \leq l$），你可以选择一个玩偶 $j$，在第 $a_i$ 秒结束后立刻把它的危险值清零，即 $d_j := 0$。

定义整体危险值为当前所有玩偶危险值的最大值：

$max_{1 \leq j \leq m} d_j$

若在第 l 秒结束后（即夜晚结束时）整体危险值大于 x，你就会失败。

请你求最小的 x，使得无论玩偶如何行动（每秒给谁加 1），你都能通过选择每次手电筒照射对象，保证最终整体危险值不超过 x。

输入格式

第一行一个整数 $t$（$1 \leq t \leq 10^4$），表示测试组数。

每组测试：

1. 一行三个整数 $n, m, l$（$1 \leq n, m, l \leq 2 * 10^5$，$n \leq l$，$1 \leq m * l \leq 2 * 10^5$）；
2. 一行 n 个整数 $a_i$（严格递增，且 $1 \leq a_i \leq l$）。

保证所有测试中 $m * l$ 的总和不超过 $2 * 10^5$。

输出格式

每组输出一个整数，表示最小可保证的 x。

样例

输入：

7
1 2 10
10
5 1 32
1 4 9 16 25
2 3 40
13 37
2 2 7
6 7
8 5 60
3 17 20 28 36 44 45 50
6 7 1987
6 7 66 77 666 777
1 1 1
1

输出：

5
7
19
1
19
1477
0

说明

第一组中，m = 2，l = 10，且只能在第 10 秒后照一次手电。10 秒后两个玩偶危险值之和是 10，因此必有一个至少为 5。你可以把危险值更高的那个清零，于是最终最大值不超过 5。并且 5 是最小可行值。