我来设计一道更有故事感、但仍适合 GESP 5 级的左边界二分题，重点保留清晰的 check 单调性和可用普通数组实现的空间。# 题目：星际救援信标

题目描述

在遥远的火星上，救援基地位于位置 0，宇宙飞船降落点位于位置 L。

为了让救援飞船能够顺利前进，火星上已经修建了 N 个信标。每个信标位于一条直线上，位置分别为：

p_1, p_2, ..., p_N

这些信标的位置已经按照从小到大的顺序给出。

救援飞船可以从一个信标飞到下一个信标。为了保证飞行安全，任意相邻两个信标之间的距离不能太大。

现在，工程师还可以在道路上增加最多 K 个信标。新增加的信标可以放在任意整数位置，但不能放在已经有信标的位置上。

请你计算：增加最多 K 个信标后，相邻信标之间的最大距离最少是多少。

注意：

• 位置 0 和位置 L 都视为已经有信标；
• 所有信标必须位于 0 到 L 之间；
• 新增信标的位置必须是整数；
• 最多可以增加 K 个信标，也可以少增加。

输入格式

第一行包含三个正整数 L、N 和 K：

• L 表示道路总长度；
• N 表示已经存在的信标数量；
• K 表示最多可以增加的信标数量。

第二行包含 N 个正整数：

p_1, p_2, ..., p_N

表示已有信标的位置，且满足：

0 < p_1 < p_2 < ... < p_N < L

输出格式

输出一个整数，表示增加最多 K 个信标后，相邻信标之间的最大距离的最小值。

样例输入

20 2 3
6 14

样例输出

4

样例说明

原来的信标位置包括：

0、6、14、20

相邻信标之间的距离为：

6、8、6

可以增加 3 个信标，例如放在：

4、10、17

此时所有信标的位置为：

0、4、6、10、14、17、20

相邻信标之间的距离为：

4、2、4、4、3、3

最大距离为 4。

无法通过增加不超过 3 个信标，使最大距离小于 4，因此答案是：

4

数据范围

对于所有测试数据：

• 1 ≤ L ≤ 10^9
• 1 ≤ N ≤ 10^5
• 0 ≤ K ≤ 10^9
• 0 < p_1 < p_2 < ... < p_N < L

补充说明

如果两个相邻信标之间的距离为 d，希望将这段距离划分成每段不超过 x 的若干段，那么至少需要增加：

(d - 1) / x

个信标。

例如：

• 当 d = 10，x = 4 时，需要增加 2 个信标；
• 当 d = 10，x = 3 时，需要增加 3 个信标。