Taein 的衣柜里挂着 $N$ 件衣服。目前，从左往右数第 $i$ 件衣服的颜色为 $c_i$。
如果存在一个整数 $k$（$1 \le k \le N$）满足 $c_1 \leq c_2 \leq \cdots \leq c_k \geq c_{k+1} \geq \cdots \geq c_N$，Taein 就会认为他的衣柜是美丽的。
然而，将衣柜整理成美丽的状态相当繁琐。因此，Taein 决定从衣柜中移走至多 $M$ 件衣服，使得剩下的衣服几乎美丽。
在移走至多 $M$ 件衣服后，设剩下的衣服数量为 $L$，且从左往右数第 $j$ 件衣服的颜色为 $d_j$。如果两件相邻衣服的颜色差至多为 $x$，Taein 就会认为它们的颜色相同。换句话说，如果存在一个整数 $k$（$1 \le k \le L$）满足以下条件，则称衣柜是几乎美丽的：
- 对于每个满足 $1 \leq j < k$ 的整数 $j$，有 $d_j - d_{j+1} \leq x$。
- 对于每个满足 $k \leq j < L$ 的整数 $j$，有 $d_{j+1} - d_j \leq x$。
请找出通过移走至多 $M$ 件衣服，能使衣柜变得几乎美丽的非负整数 $x$ 的最小值。
输入格式
第一行包含两个由空格隔开的整数 $N$ 和 $M$。
第二行包含 $N$ 个由空格隔开的整数 $c_1, c_2, \ldots, c_N$。
输出格式
输出能使衣柜变得几乎美丽的 $x$（$x \ge 0$）的最小值。
数据范围
- $1 \leq N \leq 10^5$
- $0 \leq M \leq N$
- $1 \leq c_i \leq 10^9$（$1 \leq i \leq N$）
子任务 1（4 分）
$M=0$
子任务 2（21 分）
$1 \leq N \leq 1\,000$
子任务 3（16 分）
$1 \leq c_i \leq 100$（$1 \leq i \leq N$）
子任务 4（59 分）
无附加限制。
样例
输入 1
10 2 4 2 7 15 3 11 12 10 2 6
输出 1
2
说明
当 $x=2$ 时，Taein 可以通过移走从左往右数第 5 件和第 9 件衣服来使衣柜变得几乎美丽。不存在更小的 $x$ 值能使衣柜变得几乎美丽。