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

题目背景

题目背景太长了，不写了。

题目描述

数组 $a$ 里有 $n$ 个互不相同的正整数，你需要在里面选出 $k$ 个数，使得没有两个相邻的数被选中，最小化这 $k$ 个数中最大值和最小值的差。

输入格式

第一行输入两个正整数 $n,k$。
第二行$n$ 个正整数，第 $i$ 个整数表示数组中第 $i$ 个数 $a_i$。

输出格式

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

9 5
99 82 44 35 3 11 45 1 4

96

提示

样例解释

只有一种选法：选择第 $1,3,5,7,9$ 个数，即 $99,44,3,45,4$。

数据范围

对于 $12\%$ 的数据，保证 $n \le 6$。

对于 $36\%$ 的数据，保证 $n \le 100$。

对于另外 $4\%$ 的数据，保证 $k = \lceil\frac{n}{2}\rceil$。

对于另外 $12\%$ 的数据，保证 $a_i$ 单调递增。

对于 $76\%$ 的数据，保证 $n \le 10^3$。

对于 $100\%$ 的数据，保证 $1 \le n \le 10^5$，$1 \le k \le \lceil\frac{n}{2}\rceil$，$1 \le a_i \le 10^9$，$a_i$ 互不相同。