题目描述

农夫约翰搭建了一间有 N 间牛舍的小屋。牛舍排在一条线上，第 i 号牛舍在 xi 的位置。但是他的 C 头牛并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。约翰决定自己给牛分配牛舍，使任意两头牛之间的最小距离尽可能的大。那么，这个最大的最小距离是多少呢？

输入格式

• 第 1 行: 两个用空格隔开的整数: N 和 C
• 第 2 到 n+1 行: 每行一个整数 xi

样例输入

5 3
1
2
8
4
9

样例输出

3

数据范围

2 <= N <= 100,000

2 <= C <= N

0 <= xi <= 1,000,000,000