时间限制：1000ms　内存限制：512MB

题目描述

程老师带 $n$ 个学生去外地研学。出发前，他给每个学生做了一次团队协作能力测试，得到了一个"默契值"。第 $i$ 个学生的默契值记为 $a_i$。

到了目的地，程老师需要把这 $n$ 个学生分成若干个小组来完成不同的研学任务。他对分组有几个要求：

第一，必须恰好分成 $k$ 个小组，不多不少。第二，每个小组至少要有 $1$ 个学生。第三，也是最关键的一点——分组完全自由。程老师可以把任意学生分到任意一个组里，完全不受名单顺序的约束。换句话说，名单上排第 3 个的学生和排第 57 个的学生完全可以分在同一组，只要程老师觉得这样分合理。

分好组之后，每个小组内部会有一个"磨合成本"。这个成本是怎么算的呢？一个小组里，默契值最高的学生和默契值最低的学生之间的差距，就是这个小组的磨合成本。差距越大，说明组内成员能力差异越大，磨合起来就越困难。如果一个小组只有一个人，那不存在高低之分，磨合成本就是 $0$。

程老师当然希望每个小组都尽量和谐，但他同时面对 $k$ 个小组，不可能只盯着一个组优化。他真正关心的是：所有小组中，磨合成本最大的那个是多少？ 他希望这个"最大的磨合成本"尽可能小。也就是说，即使最不和谐的那个组，也要尽量控制在一个可接受的范围内。

现在，请你帮程老师算一算：在所有可能的分组方案中，各组磨合成本的最大值最小能做到多少？

输入格式

第一行两个整数 $n$ 和 $k$，分别表示学生人数和小组数。

第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示每个学生的默契值。

输出格式

一行一个整数，表示各组磨合成本最大值的最小可能值。

数据范围

• 对于所有测试点，保证 $1 \le k \le n \le 10^5$，$1 \le a_i \le 10^9$。
• 各测试点的详细限制如下：

特殊性质 A：$k = 1$。

特殊性质 B：$a_i$ 只有 $1$ 和 $2$ 两种取值。

样例

样例 1

输入

5 3
1 2 3 4 5

输出

1

样例 2

输入

6 2
5 1 9 1 9 5

输出

4

样例 3

输入

4 4
3 1 4 1

输出

0

样例 1 解释

一种最优分法是 $\{1, 2\}$、$\{3, 4\}$、$\{5\}$，三组的磨合成本分别为 1、1、0，最大值为 1。