题目描述

农夫 $John$ 建造了一座很长的畜栏，它包括 $N$ 个隔间，这些小隔间依次编号为 $x_1, x_2 , \cdots , x_N$. 但是，$John$ 的 $C$ 头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。

为了不让牛互相伤害。$John$ 决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢

输入格式

输出包含两行，第一行包含两个整数 $N$ 和 $C$ ，($2≤N≤10^5 , 2≤C≤N$)；

第二行包含 $N$ 个整数：指出了 $x_i$ 的位置($0≤x_i≤10^9$)。

输出格式

一个整数，最大的最小值。

样例

输入

5 3

输出

1 2 8 4 9

3

提示

把牛放在1，4，8这样最小距离是3。