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

题目描述

宇航员强哥正在为他的太空站规划生活舱布局。太空站有 $n$ 个舱室，分别位于坐标 $x₁, x₂,...,xₙ$ 处。现在有$m$位宇航员即将入驻，每位宇航员都需要独立的私人空间。

为了避免宇航员们在狭小空间产生摩擦，强哥需要找到一种舱位分配方案，使得任意两位宇航员之间的最小距离尽可能大。你能帮助强哥计算出这个最大的最小距离吗？

输入格式

n m
x₁ x₂ ... xₙ

输出格式

输出最大的最小距离值

样例解释

5 3
1 2 8 4 9

3

数据范围

• $2 ≤ n ≤ 10⁵$
• $2 ≤ m ≤ n$
• $0 ≤ xᵢ ≤ 10⁹$
• 舱室位置不一定按顺序排列