CF1329E Dreamoon Loves AA

有一个仅包含字符 'A' 和 'B' 的长度为 $n + 1$ 的字符串。其中第一个和最后一个字符都为 'A'。 给出 $m$ 个下标 $p_1, p_2, \ldots, p_m$ （下标从 $0$ 开始），表示这个字符串中其它 'A' 的位置。 我们设两个相邻的 'A' 距离最小值为 $l$，距离最大值为 $r$。 举例来说，对于字符串 $\texttt{ABBAABBBA}$，$(l, r) = (1, 4)$。 我们定义一个字符串的平衡度为 $r - l$ 的值。 现在，Dreamoon 想要将字符串中的恰好 $k$ 个字符从 'B' 修改成 'A'，使得这个字符串的平衡度尽可能小。 请计算可能达到的最小平衡度。

第一行输入一个整数 $t ~ (1 \le t \le 400\ 000)$，表示测试数据组数。 对于每组测试数据，第一行输入三个整数 $n, m, k ~ (1 \le n \le 10 ^ {15}; 0 \le m \le 400\ 000; 0 \le k \lt n - m)$。 第二行输入 $m$ 个整数 $p_1, p_2, \ldots, p_m ~ (0 \lt p_1 \lt p_2 \lt \ldots \lt p_m \lt n)$。 每组测试数据的 $m$ 之和不超过 $400\ 000$。

对于每组测试数据，输出一个整数，表示将 $k$ 个 'B' 修改为 'A' 后能达到的最小平衡度。