背景

长安广月晴，留身影，琵琶行，酒客半醒。
问你看不清，朱纱帐，翠丝绦，飞天降临。
美人腰肢半倾璎珞脆，纤手独举琵琶跪，眸眼还生魅。
麝香抹唇酒更醉，醉灯彩越乱越美。

——银临《长安幻世绘》

题目描述

共有 $n$ 个彩灯从左到右排成一排，从左到右用 $1$ 到 $n$ 编号，第 $i$ 个彩灯的亮度是 $a_i$。对 $1 \leq i < n$，我们说 $i$ 号彩灯和 $i + 1$ 号彩灯是相邻的。

我们保证这 $n$ 盏灯的亮度互不相同。

一组彩灯的和谐度定义为这组彩灯中亮度最大和最小的两盏彩灯的亮度之差。

扶苏想从这 $n$ 个彩灯中选出 $m$ 个互不相邻的彩灯作为一组，她希望这组彩灯的和谐度尽可能小。请你帮她求出这个最小值。

形式化地，你需要在元素互不相同的数列 $a$ 中选出一个长度为 $m$ 的元素互不相邻的子列，使得子列的极差最小。

输入格式

第一行是两个整数，依次表示彩灯的个数 $n$ 和挑出彩灯的个数 $m$。
第二行有 $n$ 个整数，第 $i$ 个整数表示彩灯 $i$ 的亮度 $a_i$。

输出格式

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

5 3
1 2 3 4 5

4

6 3
1 7 8 3 4 6

4

见附加文件中的 D3.in

见附加文件中的 D3.ans

提示

样例 1 解释

只能选择第 $1, 3, 5$ 个彩灯。因为其他的选法都会导致有灯相邻。

样例 2 解释

可以选择第 $2, 4, 6$ 个彩灯，彩灯的亮度是 $7, 3, 6$，其极差是 $4$。

数据规模与约定

• 对 $12\%$ 的数据，保证 $n \leq 6$。
• 对 $36\%$ 的数据，保证 $n \leq 100$。
• 另有 $4\%$ 的数据，保证 $m = \lceil\frac{n}{2}\rceil$。
• 另有 $12\%$ 的数据，保证 $a_i$ 单调递增。
• 对 $76\%$ 的数据，保证 $n \leq 10^3$。
• 对 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq m \leq \lceil\frac{n}{2}\rceil$，$1 \leq a_i \leq 10^9$，$a_i$ 互不相同。