题目描述

对于给定的一个长度为 N 的正整数数列 a[1..N]，内容本身已经有序，数列为非下降序列。现要从中选出 M 个数构成一个新的数列，不改变它们在原数列中的顺序，要求新数列数项之间差值的最小值的最大值。

例如一数列 {11,24,43,52,67,81,92,97} 要从中选出 4 个数字构成新的数列。

如果新数列为：{11,24,67,97} ,新数列的差为：{13,43,30} ，最小值为 13 (最小值一定是出现在相邻数项之间，所以，我们只需要关注相邻数项的差即可）。

如果新数列为：{11,43,81,97} ,相邻项的差为：{32,38,16}，最小值为 16 。

如果新数列为：{11,43,67,97} ,相邻项的差为 {32,24,30}，最小值为 24 。

并且无论如何分段，差值的最小值不会大于 24 。

所以可以得到要在数列 {11,24,43,52,67,81,92,97} 中选 4 个数字，数项之间的差的最小值最大为 24 （也就是说差的最小值不超过 24 ）。

数据范围

对于 100% 的数据，1≤ M ≤ N≤ $10^5$ , $a_i$ ≤ $10^8$

输入格式

第 1 行包含两个正整数 N , M 。

第 2 行包含 N 个空格隔开的非负整数 $a_i$，含义如题目所述。

输出格式

一个正整数，新数列的相邻项的差的最小值的最大值。

样例

8 4
11 24 43 52 67 81 92 97

24