← 返回题目列表

Codeforces · 1329/E

E. 梦月爱AA

中文机器翻译题面 查看原题

有一个长度为 $$$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