[yLOI2022] 长安幻世绘

共有 $n$ 个彩灯从左到右排成一排，从左到右用 $1$ 到 $n$ 编号，第 $i$ 个彩灯的亮度是 $a_i$。对 $1 \leq i < n$，我们说 $i$ 号彩灯和 $i + 1$ 号彩灯是相邻的。 我们保证这 $n$ 盏灯的亮度**互不相同**。 一组彩灯的**和谐度**定义为这组彩灯中亮度最大和最小的两盏彩灯的亮度之差。 扶苏想从这 $n$ 个彩灯中选出 $m$ 个**互不相邻**的彩灯作为一组，她希望这组彩灯的和谐度**尽可能小**。请你帮她求出这个最小值。 形式化地，你需要在元素互不相同的数列 $a$ 中选出一个长度为 $m$ 的元素互不相邻的子列，使得子列的极差最小。 ## Input 第一行是两个整数，依次表示彩灯的个数 $n$ 和挑出彩灯的个数 $m$。 第二行有 $n$ 个整数，第 $i$ 个整数表示彩灯 $i$ 的亮度 $a_i$。 ## Output 输出一行一个整数表示答案。 [samples] ## Background > 长安广月晴，留身影，琵琶行，酒客半醒。 > 问你看不清，朱纱帐，翠丝绦，飞天降临。 > 美人腰肢半倾璎珞脆，纤手独举琵琶跪，眸眼还生魅。 > 麝香抹唇酒更醉，醉灯彩越乱越美。 ——银临《长安幻世绘》 ## Note ### 样例 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$ 互不相同。