有一个长度为 $$$n+1$$$ 的字符串,其中包含字符“A”和“B”。字符串的第一个字符和最后一个字符等于“A”。
给定 $$$m$$$ 索引 $$$p_1, p_2, \ldots, p_m$$$ ($$$0$$$-索引),表示字符串中字符“A”的其他索引。
让我们将两个相邻“A”之间的最小距离表示为 $$$l$$$,将相邻“A”之间的最大距离表示为 $$$r$$$。
例如,字符串“ABBAABBBA”的$$$(l,r)$$$ 为$$$(1,4)$$$。
我们将字符串的平衡度表示为 $$$r-l$$$ 的值。
现在 Dreamoon 想要将 $$$k$$$ 个字符从 'B' 精确地更改为 'A',并且他想让字符串的平衡度尽可能小。
请计算所需的平衡度的最小可能值。
输入
第一行包含一个整数 $$$t$$$ 表示测试用例的数量($$$1 \leq t \leq 400\,000$$$)。
对于每个测试用例,第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \leq n \leq 10^{15}、0 \leq m \leq 400\,000、0 \leq k < n - m$$$)。
第二行包含 $$$m$$$ 整数 $$$p_1, p_2, \ldots, p_m$$$, ($$$0 < p_1 < p_2 < \ldots < p_m < n$$$)。
$$$m$$$ 的总和最多为 $$$400\,000$$$。
输出
对于每个测试用例,打印一个整数:$$$k$$$ 'B' 变为 'A' 后平衡度的最小可能值。
示例
输入 #1
5 80 3 5 11 24 50 81 7 12 4 10 17 26 37 48 61 25 10 14 3 4 7 12 13 15 17 19 21 23 1 0 0 10 2 0 2 4
输出 #1
5 2 0 0 4