题目描述

强哥是一位数学天才，最近他迷上了一个有趣的游戏。他手中有一个长度为 n 的数字序列，序列中的每个数字都是正整数。强哥发现，通过巧妙地删除序列中的某些数字，可以使得剩余数字的最大值与最小值之间的差距变得非常小。为了增加游戏的挑战性，强哥决定删除恰好 k 个数字，但他希望在删除后，剩余数字的最大值与最小值之差尽可能小。

强哥需要你的帮助。请你为强哥设计一个策略，找到一种最优的删除方式，使得在删除 k 个数字后，剩余数字的最大值与最小值之差最小。

输入格式

$n,k$

$a_1,a_2,a_3,...,a_n$

$1≤k≤n≤2*10^5$

$1≤a_i≤10^9$

输出格式

输出一个整数，表示答案

5 2
4 5 1 3 9

2

7 3
31 24 26 6 18 22 13

8

提示