宝藏探险

题目描述

Alice和Bob正在一个一维数轴上探索宝物，Alice从数轴的左端开始向右探索，Bob从数轴的右端开始向左探险。每次探险，Alice和Bob都会记录下当前点的辐射值。

但是由于Alice和Bob关系很差，所以他们会保持中间至少存在 $k$ 个点，也就是说，假设Alice探索到 $P$ 点时，Bob最多探索到 $P + k + 1$ 就会停下。也就是说，中间一定会有 $k$ 个点没有被探索。

我们将一次探险的辐射最大值和辐射最小值之差称之为宝藏值，宝藏值越小，则说明这块区域越可能存在宝藏。换句话说，宝藏值的计算值如下公式所述：

我们假设Alice探索过的点的集合构成 $S_1$， Bob探索过的点构成的集合构成 $S_2$，则宝藏值为：

现在，你可以任意安排Alice和Bob的探索进度，但是必须保证数轴的 $n - k$ 个点被探索过，且Alice和Bob必须都至少探索过一个点，请你求出最小的宝藏值是多少。

输入格式

第一行包含2个整数 $n$ 和 $k$，意义如上所述。 第二行为 $n$ 个整数 $a_i$，表示第 $i$ 个点的宝藏值。

数据范围：

$3 \le n \le 10^5$ $1 \le k \le n - 2$ $1 \le a_i \le 10^6$

输出格式

一个整数，表示最小可能探索到的宝藏值。

样例 #1

样例输入 #1

10 2
3 6 4 6 5 1 9 3 7 4

样例输出 #1

4

提示

最优的情况是Alice探险点 1 - 5，Bob探险点 8 - 10。 这样 $S_1 = \{3,6,4,6,5\}$，$S_2 = \{3,7,4\}$。

$\max(S_1 \cup S_2) = 7， \min(S_1 \cup S_2) = 4$

因此 $f = 7 - 4 = 3$。可以证明这是可能的最小值。