该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一个遥远的星球上，有一个名为卡尔达西的小村庄。这个村庄建有 $n$ 个独立的居住单元，沿着一条直线排列，每个单元 $i$ 位于位置 $x_i$。村庄的 $m$ 只宠物龙对这种排列方式感到不满，因此它们经常互相争斗。为了避免龙之间的争斗，村长决定将每只宠物龙安置在尽可能远离其他龙的居住单元中，从而最大化两只最近的龙之间的距离。

村民们为了龙的安全和和平相处，希望找到一种方案，使得任意两只龙之间的最小距离尽可能大。村长现在想知道，在最佳安置方案下，这个最大的最小距离是多少？

输入格式

第一行两个整数 $n$ 和 $m$，其含义见题目描述；

第二行为 $n$ 个整数，表示居住单元的位置 $x_i$。

输出格式

输出仅一个整数，表示答案。

【样例 1 输入】

5 3
1 2 8 4 9

【样例 1 输出】

3

【样例 1 解释】

放置在 1, 4 ,8 这样最小距离是 3 。

【数据范围】

对于10%的数据，$2 \leq n \leq 20, 0 \leq x_i \leq 10^4, 2\leq m \leq n$。

对于40%的数据，$2 \leq n \leq 10^3, 0 \leq x_i \leq 10^4, 2\leq m \leq n$。

对于100%的数据，$2 \leq n \leq 10^5, 0 \leq x_i \leq 10^9, 2\leq m \leq n$。