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

题目描述

给定一个长度为 $N$ 的数列 $A$ 和一个正整数 $K$，你需要删去 $K$ 个数字，使剩下的数字的最大值与最小值之差最小。

输入格式

输入包含一行，包含 $N$、$K$ 和数列 $A$：

其中，$1 \leq K < N \leq 2 \times 10^5$，$1 \leq A_i \leq 10^9$。

输出格式

输出一个整数，表示删去 $K$ 个数字后，剩下的数列中最大值与最小值的差的最小值。

样例

5 2
3 1 5 4 9

2

6 5
1 1 1 1 1 1

0

8 3
31 43 26 6 18 36 22 13

18

提示

限制条件

• 输入数据全部为整数。
• $1 \leq K < N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$

样例解释 #1

我们需要从数列 $A = (3, 1, 5, 4, 9)$ 中删去 $2$ 个元素，剩下的数列为 $B$，使得 $B$ 中最大值与最小值的差最小。
可以选择删除 $1$ 和 $9$，这样剩下的数列是 $(3, 5, 4)$，其最大值为 $5$，最小值为 $3$，所以最大值与最小值的差为 $5 - 3 = 2$。