划分

时间限制：$2s$

空间限制：$256MB$

题目描述：

给定一个序列 $a$ ，长度为 $n$ ，我们的任务是将这个序列划分成 $k$ 段。

不妨假设一个划分为 $[1 \to r_1] ,[r_1 + 1\to r_2], .. [r_{k-1}+1\to r_k]$，显然 $r_k = n, r_0 = 0$

第$i$段的$b_i$为第$i$段中的最大值$-$第$i$段中的最小值

形式化地说：

记划分的第 $i$ 段 （$i \ge 1$）

$$b_i = \max_{i \in [r_{i-1} + 1 \to r_i]} a_i - \min_{i \in [r_{i - 1} + 1\to r_i]} a_i $$

一种合法的划分的代价为划分的段中$b_i$的最大值

形式化地说：

$$B = \max_{i = 1} ^ k b_i$$

请输出合法划分的最小代价

输入描述：

第一行两个整数n, k，如题所示。
第二行给出n个整数，表示序列a。

输出描述：

一行，表示B的最小可能值

样例输入：

5 3 
-20 12 3 12 100

样例输出：

9

样例解释

一种可行的划分如下，可以证明不存在更小的B的划分：

-20 | 12 3 12 | 100

数据范围：

$20pts$ $1 \le k \le n \le 23$

$40pts$ $1 \le k \le n \le 200$

$60pts$ $1 \le k \le n \le 2000$

对于所有的数据 $1 \le k \le n \le 5\times10^5, a_i \in [-10^9, 10^9]$