时间限制： 1.0 秒

空间限制： 512 MB

题目描述

Treasure Hunters 公司热衷于探索地球上的宝藏，目前他们正在一个区域进行探索。

这个区域可以被抽象为一段一维数轴，公司在这段区域均匀打下了 $n$ 个探测点，公司会在每个探测点进行一次能量探测。最终，这块区域中最高能量与最低能量的差标志着这块区域的稳定值，稳定值越高，就代表这块区域越有可能拥有宝藏。

Treasure Hunters 公司有两位资深的探测员 Alice 和 Bob，他们会分别从这块区域的左右两端开始向中间逐步进行探测。可惜的是，这两位探测员由于竞争关系非常不和睦，他们不愿意出现在距离对方 $k$ 个探测点的距离之内。所以，当他们发现双方之间有 $k$ 个探测点的时候，就会在探测完当前探测点之后就结束探测工作，返回公司汇报结果。

这当然导致了这块区域中会有 $k$ 个探测点没有被探测到，因此导致稳定值的结果出现偏差。然而，由于每个探测点的探测时间不确定，最终是哪 $k$ 个探测点没有被探测到是未知的。你的任务就是求出汇报的稳定值的最小可能值。

注：两位探测员都至少探测一个点。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $n,k$，分别代表探测点的总个数和未被探测到的个数。已知 $1\leq k\leq n-2$。

第二行包含 $n$ 个整数 $w_1,w_2\cdots,w_n$ 表示 $n$ 个探测点的能量值。

输出格式

输出到标准输出。

输出一个整数，表示两位探测员汇报的稳定值的最小可能值。

6 2  
3 5 7 6 2 4

3

样例 1 解释

可能出现的探测情况如下：

所以最小可能的稳定值为 $3$。

子任务

对于 $40\%$ 的数据，保证 $n\le 100$。

对于 $70\%$ 的数据，保证 $n\le 5\times 10^4$。

对于 $100\%$ 的数据，保证 $n\le 10^6,1\le k\le n-2,~1\le w_i\le 10^9$。

提示

本题输入量较大，请采用效率较高的读入方式。