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

题目描述

有 $n$ 个服务器节点排成一条直线，已知它们的位置分别为 $p₁, p₂, …, pₙ$（未排序）。现在需要在这 $n$ 个节点上部署 $m$ 个服务实例，每个节点最多部署一个实例。为了防止服务之间的信号干扰，我们希望任意两个实例所在节点之间的距离尽可能大。 任务是：找到一个部署方案，使得任意两个实例之间的最小距离最大，并输出这个最大的最小距离。

输入格式

第一行两个整数 $n$ 和 $m$。

接下来 $n$ 行，每行一个整数，表示服务器节点的位置 $pᵢ$。

限制

$2 ≤ n ≤ 10⁵$

$0 ≤ pᵢ ≤ 10⁹$

$2 ≤ m ≤ n$

输出格式

一个整数，表示最大的最小距离。

样例

5 3
1
2
8
4
9

3

样例解释

将实例部署在位置 1、4、8 的节点上，它们之间的最小距离为 3。可以证明这是能够达到的最大值。