U160775 花里胡哨的Peter

> 这道题是我们学长出的，只是出得不太好。 > > ——伟大的信息学导师 $\Huge\color{#ec2}\underline\bold{drq}$

有一天， Peter 想出了一个使作业变得有趣的方法：隔几道题目写一道，让作业稀疏而不失韵味。他于是马上把这种方法运用到了作业中。 现在， Peter 的练习本上有 $N$ 道题，且题目之间各有空隙 （指两题之间的空间，如位置 $1$ 和 $4$ 之间间隙为 $2$），而他**不多不少**想写 $M$ 道题，已知题目在练习本上的位置 $a_1,a_2,...,a_{N-1},a_N$，求两道写了的题中**最小空隙的最大值**。

输入的第一行是两个整数 $N$ 和 $M$ ，分别表示练习本的题目数和 Peter 想写的题目数。 输入的第二行是 $N$ 个整数 $a_i$ ，表示第 $i$ 道题在练习本上的位置。

输出仅一个整数，表示所有相邻的题目的最小空隙的最大值。

### 样例1说明 Peter 写完位置 $1,4,7$ 的 $3$ 道题目。$1$ 和 $4$ 之间间隙为 $2$，$4$ 和 $7$ 之间间隙为 $2$，最小间隙为 $2$，在所有的方法中最大。 ### 样例2说明 Peter 写完位置 $1,16,32,64$ 的 $4$ 道题目。$1$ 和 $16 $ 之间间隙为 $14$，$16$ 和 $32$ 之间间隙为 $15$，$32$ 和 $64$ 之间间隙为 $31$，最小间隙为 $14$，在所有的方法中最大。 ### 数据范围 **2022-3-25 进行了加强**。 对于 $30\%$ 的数据，$2 \leq M \leq N \leq 100$ ， $0 \leq a_i \leq 10^3$； 对于 $70\%$ 的数据，$2 \leq M \leq N \leq 10^4$ ， $0 \leq a_i \leq 10^5$； 对于 $100\%$ 的数据，$2 \leq M \leq N \leq 5\times10^5$ ， $0 \leq a_i \leq 10^9$，且保证数组 $\{a_i\}$ 单调递增。 >这题是本人一年前的傻逼时期乱搞的还跟其它题类似，以后再也不弄这种傻逼题了。操。 > > ——愚蠢的信息学废物 $\small\color{#960}\underline\bold{caibyte}$