题目描述

小珅是一个热爱编程课的小学生。

今天编程老师给大家布置了N道练习题，题目按照顺序依次编号为1到N，每一道都有一个难度系数$a_i$，难度系数越低，这道题越简单，如果难度系数为负数，说明这道题非常简单。

小珅平时很爱做题，为了保持专注，他一定会按照老师布置的顺序做题，但是如果连续的两道题的难度差距太大，小珅会感觉不适，小珅的不适值c(a)定义为相邻题目难度差的最大值，可以用如下的公式表示：

$c(a)=1\le i\lt nmax|a_i+1-a_i|$

为了缓解这种症状，老师允许小珅在做题之前选择最多k道练习题，把它们替换成题库中的其他题目。由于题库的题目非常多，小珅可以把题目替换成任意他想设定的难度。

小珅现在想知道，他替换掉题目之后，不适值最小是多少。

输入格式

输入共 2 行，第一行包含两个正整数 N和k，表示题目的数量和最大可以替换多少题。

接下来 1 行，一共N个正整数，表示每道题的难度$a_i$。

输出格式

输出共 1行，一个数字，表示不适值的最小值。

样例输入

6 3
1 2 3 7 8 9

样例输出

1

提示

小珅可以替换掉后3题，最后可以得到1,2,3,4,5,6。

对于 20% 的数据，保证$1\lt N\le 10$。

另有 15% 的数据，保证 $1\le k\le 3$。

对于 60% 的数据，保证 $1\lt N\le 500$。

对于 100% 的数据，保证 $1\lt k\le N\le 2000$，$-10^{9}\le a_i\le 10^{9}$。

6 3
1 2 3 7 8 9

1

3 1
-100 0 100

100

4 1
1 100 1 100

99