共有 n 个风铃悬挂在屋檐下,每个风铃都能发出一定音调的声音。从左到右给风铃从 1 至 n 编号,第 i 个风铃的音调是 a_i 。
为了表达内心的思念,扶苏决定在 n 个的风铃中取出 m 个,送给远方的朋友。
请你找到最小的整数 \varepsilon ,使得存在一种方案,能够从 n 个风铃中挑出 m 个,设挑出风铃的音调为 b_1, b_2, \dots b_m ,满足对任意的 1 \leq i, j \leq m ,都有 |b_i - b_j| \leq \varepsilon 。
第一行是两个整数,表示风铃的个数 n 和挑选出风铃的个数 m 。 第二行有 n 个整数,表示每个风铃的音调。第 i 个整数表示 a_i 。
输出一行一个整数,表示最小的 \varepsilon 。
5 3 1 2 3 4 5
2
6 4 1 7 8 3 4 6
4
一种选择的方案是选择第 2,4,5,6 四个风铃,音调依次为 7,3,4,6 。可以得到对任何的 1 \leq i, j\leq 4 ,都有 |b_i - b_j| \leq 4 。
另一种方案是选择第 2,3,5,6 四个风铃,同样计算得到的 \varepsilon 为 4 。