共有 n 个彩灯从左到右排成一排,从左到右用 1 到 n 编号,第 i 个彩灯的亮度是 a_i 。对 1 \leq i < n ,我们说 i 号彩灯和 i + 1 号彩灯是相邻的。
我们保证这 n 盏灯的亮度互不相同。
一组彩灯的和谐度定义为这组彩灯中亮度最大和最小的两盏彩灯的亮度之差。
扶苏想从这 n 个彩灯中选出 m 个互不相邻的彩灯作为一组,她希望这组彩灯的和谐度尽可能小。请你帮她求出这个最小值。
形式化地,你需要在元素互不相同的数列 a 中选出一个长度为 m 的元素互不相邻的子列,使得子列的极差最小。
第一行是两个整数,依次表示彩灯的个数 n 和挑出彩灯的个数 m 。 第二行有 n 个整数,第 i 个整数表示彩灯 i 的亮度 a_i 。
输出一行一个整数表示答案。
5 3 1 2 3 4 5
4
6 3 1 7 8 3 4 6
只能选择第 1, 3, 5 个彩灯。因为其他的选法都会导致有灯相邻。
可以选择第 2, 4, 6 个彩灯,彩灯的亮度是 7, 3, 6 ,其极差是 4 。