E - Make Them Narrow Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

長さ N の数列 A が与えられます。
A のうち丁度 K 要素を自由に選んで消し、残った要素を順序を保って連結した数列を 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) から丁度 2 要素を自由に選んで消すことを考えます。

  • 例えば 2 要素目の 1 、 5 要素目の 9 を消すと、消した後の数列 B=(3,5,4) となります。
    • このとき B の最大値は 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

Score : 250 points

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