题目描述

你得到一个长度为 $N$ 的序列 $A$。从 $A$ 中自由选择恰好 $K$ 个元素并移除它们，然后将剩余元素按原顺序连接形成新序列 $B$。

找出以下值的最小可能值: $B$ 的最大值减去 $B$ 的最小值。

输入格式

输入从标准输入中以下列格式给出:

$N$ $K$

$A_1$ $A_2$ $\dots$ $A_N$

输出格式

将答案作为整数输出。

输入输出样例 #1

输入 #1

5 2
3 1 5 4 9

输出 #1

2

输入输出样例 #2

输入 #2

6 5
1 1 1 1 1 1

输出 #2

0

输入输出样例 #3

输入 #3

8 3
31 43 26 6 18 36 22 13

输出 #3

18

说明/提示

样例 1 解释

考虑从 $A=(3,1,5,4,9)$ 中恰好移除两个元素。

• 例如,如果你移除第 2 个元素 1 和第 5 个元素 9,得到的序列是 $B=(3,5,4)$。
  • 在这种情况下, $B$ 的最大值是 5,最小值是 3，所以 (B 的最大值) - (B 的最小值) = 2，这是最小可能值。

数据范围

• 所有输入都是整数。
• $1\ \le\ K\ <\ N\ \le\ 2\ \times\ 10^5$
• $1\ \le\ A_i\ \le\ 10^9$