题目描述

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

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

输入格式

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

$N$ $K$

$A_1$ $A_2$ $\cdots$ $A_N$

输出格式

将答案作为整数输出。

样例

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解释

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

例如,如果你移除第2个元素 1 和第5个元素 9,得到的序列是 B=(3,5,4)。

• 在这种情况下,B 的最大值是 5,最小值是 3,所以 (B 的最大值) - (B 的最小值) = 2,这是最小可能值。

数据范围

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

来源

• AtCoder ABC361C