Description

在虚拟世界里，怪兽占据了地球的整个领土，严重威胁了富强民主文明和谐自由平等公正法治社会，为解决这个问题，国家决定发明一个终极武器，消灭怪兽。由于经费有限，你只有x个设备需要完美的安排在L个地点，使两个设备间的最小距离尽可能大。

Format

Input

第一行输入L（2<=L<=1e6）个地点和你拥有的设备数x（2<=x<=L）

第二行输入L（0<=Li<=1e6）个地点的地理位置，其中地点以行排列

Output

输出一个整数表示最大化的两个设备之间的最下距离

Samples

5 3 
2 3 9 6 11

4

4 3
1 4 9 10

3

Hint

第一个样例中你可以把武器安置在2 6 11点