你好！我是你的OI金牌教练。

刚才在推演过程中，为了展示排错思路显得有些冗长。这里为你提供修正后、精简且完全正确的版本。

这道题目结合了汉朝经略河西走廊的历史背景，考察 GESP 6级 中非常重要且高频的算法——二分答案 (Binary Search on Answer)。

这道题目符合 GESP 6级 难度，考察的是如何将“最优化问题”转化为“判定问题”，从而利用二分法将时间复杂度从指数级或多项式级降低到对数级。

第一部分：背景知识讲解

1. 河西走廊与烽燧 (Hexi Corridor & Beacons)

汉武帝时期，霍去病击败匈奴，汉朝夺取了河西走廊（今甘肃一带），设立了“河西四郡”（武威、张掖、酒泉、敦煌）。为了巩固防线，汉朝修筑了大量的烽燧（烽火台）。

2. 防线布局的智慧

烽燧是古代的信息传递节点。为了让整条防线的预警能力最强，在有限的兵力和资源下（即只能驻守有限个烽燧），大将军希望相邻烽燧之间的距离尽可能均衡且足够远，避免某些路段因为烽燧过密而浪费，或因为过疏而形成防守漏洞。

3. 算法模型：最大化最小值

在算法竞赛中，当我们遇到**“求最大的最小值”或者“求最小的最大值”这类问题时，99% 的情况下是在考察二分答案**。

• 直接求“最大间距”很难。
• 但是，如果我们假设一个间距 $D$，去验证“能否选出 $M$ 个点，使得任意相邻间距都 $\ge D$”，这通常很容易（使用贪心法）。
• 利用答案的单调性，我们可以通过二分查找来逼近最优解。

第二部分：题目内容

题目名称：河西烽火 (Beacons of Hexi)

题目描述

河西走廊地形狭长，我们可以将其抽象为一条数轴。 汉朝工部勘探出了 $N$ 个适合修建烽燧的候选位置，它们的坐标分别为 $X_1, X_2, \dots, X_N$。

汉武帝下旨，要求在这些候选位置中选出 $M$ 个位置修建烽燧。为了保证防线覆盖范围最大且无死角，要求选出的 $M$ 个烽燧中，任意两个相邻烽燧之间的距离都不能太小。

具体来说，假设选出的 $M$ 个烽燧坐标从小到大排序后为 $P_1, P_2, \dots, P_M$，那么这套方案的“防线强度”定义为：所有相邻烽燧距离的最小值，即 $\min(P_{i+1} - P_i)$。

请你编写程序，帮助大将军规划选址方案，使得**“防线强度”最大**。输出这个最大的最小值。

输入格式

第一行包含两个正整数 $N, M$。

• $N$ 表示候选位置的数量。
• $M$ 表示需要修建的烽燧数量。

第二行包含 $N$ 个正整数 $X_1, X_2, \dots, X_N$，表示候选位置的坐标。 注意：输入的坐标不一定有序。

输出格式

输出一行一个整数，表示能够达到的最大的“防线强度”（即最大的最小间距）。

输入输出样例 #1

输入：

5 3
1 2 8 4 9

输出：

3

样例 #1 解释： 候选点排序后为：1, 2, 4, 8, 9。需要选 3 个。

• 方案 A：选 {1, 4, 8}。间距为 $3, 4$。最小间距为 3。
• 方案 B：选 {1, 4, 9}。间距为 $3, 5$。最小间距为 3。
• 其他方案（如 {1, 2, 4} 最小间距 1）均不如上述方案优秀。 故答案为 3。

输入输出样例 #2

输入：

6 4
1 4 9 15 20 25

输出：

6

样例 #2 解释： 需要选 4 个点。

• 选 {1, 9, 15, 25}：间距为 $8, 6, 10$。最小间距为 6。
• 若试图让间距达到 7：从 1 开始，下一个必须 $\ge 8$ (选9)，再下一个 $\ge 16$ (选20)，再下一个 $\ge 27$ (无点可选)。无法选出 4 个。 故答案为 6。

数据范围

对于 $100\%$ 的数据：

• $2 \le N \le 10^5$
• $2 \le M \le N$
• $0 \le X_i \le 10^9$