编程小组

题目背景

比赛结束后，云南大学校队打算组织一场编程交流活动，将参赛选手分成若干小组进行讨论。为了让每个小组的讨论质量更高，队员们希望每个小组内选手的水平差距不要太大。

题目描述

有 $n$ 名选手，第 $i$ 名选手的编程水平为 $a_i$。现在要将所有选手分配到不超过 $m$ 个学习小组中，每个小组至少包含一名选手，且小组内的选手按水平排序后必须是连续的（即只能将排序后相邻的选手分到一组）。小组内选手的编程水平差距定义为该小组内最大值与最小值的差。

一个分配方案的「不和谐度」定义为所有小组水平差距的最大值。请你求出最小的不和谐度。

输入格式

第一行两个整数 $n, m$（$1 \le m \le n \le 2\times 10^5$），表示选手人数和最多可分的小组数。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示每位选手的编程水平。

输出格式

输出一个整数，表示最小的不和谐度。

样例

5 2
1 3 5 7 9

4

6 3
10 20 10 30 40 10

10