Score : $250$ points

问题陈述

给定一个长度为 $N$ 的序列 $A$。 从 $A$ 中自由选择恰好 $K$ 个元素并移除它们，然后将剩余的元素按照原始顺序连接起来，形成一个新的序列 $B$。 找到这个的最小可能值：$B$ 的最大值减去 $B$ 的最小值。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given a sequence $A$ of length $N$.
Freely choose exactly $K$ elements from $A$ and remove them, then concatenate the remaining elements in their original order to form a new sequence $B$.
Find the minimum possible value of this: the maximum value of $B$ minus the minimum value of $B$.

Constraints

• All inputs are integers.
• $1 \le K < N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$

Input

The input is given from Standard Input in the following format:

$N$ $K$

$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the answer as an integer.

Sample Input 1

5 2
3 1 5 4 9

Sample Output 1

2

Consider removing exactly two elements from $A=(3,1,5,4,9)$.

• For example, if you remove the 2nd element $1$ and the 5th element $9$, the resulting sequence is $B=(3,5,4)$.
  • In this case, the maximum value of $B$ is $5$ and the minimum value is $3$, so (maximum value of $B$) $-$ (minimum value of $B$) $=2$, which is the minimum possible value.

Sample Input 2

6 5
1 1 1 1 1 1

Sample Output 2

0

Sample Input 3

8 3
31 43 26 6 18 36 22 13

Sample Output 3

18