分数: 250 点
问题陈述
给你一个序列 A 长度 N.
自由选择准确 K 元素来自 A 并删除它们,然后按原始顺序连接剩余元素以形成新序列 B.
找到该值的最小可能值:最大值 B 减去最小值 B.
约束
- 所有输入均为整数。
- 1 \le K < N \le 2 \times 10^5
- 1 \le A_i \le 10^9
输入
输入由标准输入按以下格式给出:
N K A_1 A_2 \dots A_N
输出
将答案打印为整数。
示例输入 1
5 2 3 1 5 4 9
示例输出 1
2
考虑从中删除两个元素 A=(3,1,5,4,9).
- 例如,如果删除第二个元素 1 和第 5 个元素 9,结果序列是 B=(3,5,4).
- 在这种情况下,最大值 B is 5 最小值为 3,所以(最大值 B) - (最小值 B) =2,这是可能的最小值。
示例输入 2
6 5 1 1 1 1 1 1
示例输出 2
0
示例输入 3
8 3 31 43 26 6 18 36 22 13
示例输出 3
18