题目描述

小珅建造了一座有n间牛舍的小屋，牛舍排在一条直线上，第i间牛舍在xᵢ的位置，但是小珅的m头牛对小屋很不满意，因此经常互相攻击。小珅为了防止牛之间互相伤害，决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。

牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害，小珅决定给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的和最小距离是多少呢？

输入格式

第一行用空格分隔的两个整数n和m；

第二行为n个用空格隔开的整数，表示位置xᵢ。

输出格式

输出仅一个整数，表示最大的最小距离值。

输入样例 #1

12 8
1
3
6
11
18
27
38
41
56
73
92
113

输出样例 #1

10

输入样例 #2

5 3
1 2 8 4 9

输出样例 #2

3

输入样例 #3

6 4
10 20 30 40 50 60

输出样例 #3

10

提示

【样例说明】：把牛放在1,4,8这样最小距离是3。

说明/提示：2≤n≤10⁵，0≤xᵢ≤10⁹，2≤m≤n。

数据范围

说明/提示：2≤n≤10⁵，0≤xᵢ≤10⁹，2≤m≤n。