题目描述

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

你需要从 $A$ 中恰好移除 $K$ 个元素，剩余的 $N-K$ 个元素按原有的相对顺序连接组成一个新的序列 $B$。

请计算出 $B$ 中最大值与最小值之差的最小值。

输入格式

第一行包含两个正整数 $N$ 和 $K$。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$ —— 表示序列 $A$ 的元素。

输出格式

输出一个整数，表示在所有可能的移除方案中，序列 $B$ 的极差（最大值减去最小值）的最小值。

样例输入 1

5 2
3 1 5 4 9

样例输出 1

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

说明

样例解释

• 在第一个样例中，从 $A=(3, 1, 5, 4, 9)$ 中移除两个元素。如果移除第 $2$ 个元素 $1$ 和第 $5$ 个元素 $9$，剩余序列为 $B=(3, 5, 4)$。此时 $B$ 的最大值为 $5$，最小值为 $3$，差值为 $2$，这是所有移除方案中的最小值。

数据范围

对于所有测试点，保证：

• $1 \le K < N \le 2 \times 10^5$。
• $1 \le A_i \le 10^9$。
• 保证所有的输入值均为整数。