和谐分组

题目描述

珅泽教育五级班共有 n 名学生，按照学号从 1 到 n 的顺序，每名学生的身高分别为 $a_1$、$a_2$、……、$a_n$。由于是新学期，班级需要进行分组，分组的要求如下：

1. 进行分组的组数不能超过 k。
2. 每组的人的学号必须相邻。

由于身高差过大的人分在同一个组会激起组内内部矛盾，所以我们定义一个分组方案的不和谐度为每个组的身高极差（最高的身高减去最矮的身高）的最大值。

我们希望最小化这个不和谐度，输出这个不和谐度。

输入描述

第一行包括两个正整数 n、k。

第二行包括用空格隔开的 n 个正整数，第 i 个正整数描述学号为 i 的学生的身高。

输出描述

一行包括一个整数，表示不和谐度最小的分组方案的不和谐度。

样例

输入：

8 3
5 7 2 3 8 5 9 4

输出：

5

样例解释：一种可能的分组是 5 7 2 / 3 8 5 / 9 4。

输入样例 #2

1 1
5

输出样例 #2

0

输入样例 #3

2 2
22 72

输出样例 #3

0

数据范围

1 ≤ k、n ≤ 10^5，$a_i$ ≤ 10^9。