让极差最小

题目描述

给定长度为 $N$ 的序列 $A$。

从 $A$ 中自由选择恰好 $K$ 个元素并删除,然后将剩余元素按原顺序拼接,形成新序列 $B$。

求 $B$ 的最大值减去 $B$ 的最小值的最小可能值。

输入格式

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

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$

输出格式

以整数输出答案。

样例

5 2
3 1 5 4 9

2

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

例如,若删除第 2 个元素 $1$ 和第 5 个元素 $9$,得到的序列为 $B=(3,5,4)$。

此时 $B$ 的最大值为 $5$,最小值为 $3$,因此 $B$ 的最大值减去 $B$ 的最小值等于 $2$,这是最小可能值。

6 5
1 1 1 1 1 1

0

8 3
31 43 26 6 18 36 22 13

18

数据范围

• 所有输入均为整数。
• $1 \le K \lt N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$