该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小 Z 喜欢吃序列，他觉得一个长度为 $q$ 的序列 $p$ 的美味程度是这个序列里面相邻两个数字之差的绝对值的最大值。即

现在，小 Z 有一个长度为 $n$ 的序列 $a$，他想让你帮他找到一个 $a$ 的长度不小于 $m$ 的子序列 $b$，然后他把这个序列吃掉。因为你很坏，所以你希望帮小 Z 找到的序列 $b$ 的美味程度尽可能小。你需要输出这个美味程度。

我们称一个序列 $t$ 是一个序列 $s$ 的子序列，当且仅当 $s$ 删去若干个数（可以为 $0$ 个）后可以得到 $t$。例如，$1,2,3$，$1,3,5$ 都是 $1,2,3,4,5$ 的子序列，但 $1,3,2,5,4$ 不是。

输入格式

从 seq.in 文件读入数据。

第一行是两个整数，依次表示数列 $a$ 的长度 $n$ 和数列 $b$ 的长度 $m$。

第二行 $n$ 个整数表示 $a_1, a_2, \dots a_n$。

输出格式

输出到 seq.out 文件。

输出一行一个整数表示答案。

样例

5 3
1 5 2 4 3

1

5 3
1 5 3 4 2

2

6 4
1 9 1 9 8 1

7

样例 4

点击链接 ex_seq4.in 和 ex_seq4.ans 下载大样例 4 的输入数据和输出数据。

说明/提示

• 对 $30\%$ 的数据，保证 $n \leq 6$。
• 对 $60\%$ 的数据，保证 $1 \leq a_i \leq 25$。
• 对 $80\%$ 的数据，保证 $|a_i| \leq 10^6$。
• 对上述三档数据规模，分别存在一个测试点满足 $n = m$，共占总测试点数量的 $30\%$。
• 对 $100\%$ 的数据，保证 $2 \leq m \leq n \leq 10^3$，$-10^9 \leq a_i \leq 10^9$。