题目描述

农场主老张修建了一排共 $n$ 间牛棚，牛棚沿一条直线排列，第 $i$ 间牛棚的位置为 $x_i$。他养了 $m$ 头奶牛，但这些奶牛经常互相顶撞。为了减少冲突，老张决定把每头牛安置在尽可能远离其他牛的牛棚中。

具体来说，老张要从 $n$ 间牛棚中选出 $m$ 间，分别放入一头牛，使得任意两头牛之间的最小距离尽可能大。求这个最大的最小距离是多少。

输入格式

第一行两个空格分隔的整数 $n$ 和 $m$。

接下来 $n$ 行，每行一个整数，表示牛棚的位置 $x_i$。

输出格式

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

样例

5 3
1
2
8
4
9

3

提示

【样例解析】把牛放在位置 $1$、$4$、$8$ 的牛棚中，最小距离为 $3$。可以证明不存在更优方案。

【数据范围】对于 $100\%$ 的数据，$2 \le n \le 10^5$，$0 \le x_i \le 10^9$，$2 \le m \le n$。不保证 $x$ 数组单调递增。