该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

Treasure Hunters 公司有两位资深的探测员 Alice 和 Bob，他们会分别从这块区域的左右两端开始向中间逐步进行探测。可惜的是，这两位探测员由于竞争关系非常不和睦，他们不愿意出现在距离对方 $k$ 个探测点的距离之内。所以，当他们发现双方之间有 $k$ 个探测点的时候，就会在探测完当前探测点之后就结束探测工作，返回公司汇报结果。这当然导致了这块区域中会有 $k$ 个探测点没有被探测到，因此导致稳定值的结果出现偏差。然而，由于每个探测点的探测时间不确定，最终是哪 $k$ 个探测点没有被探测到是未知的。你的任务就是求出汇报的稳定值的最小可能值。

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

输入

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

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

输出

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

样例

6 2
3 5 7 6 2 4

3

样例解释

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

提示

$40\%$ 的测试数据满足 $n \le 100$；

$70\%$ 的测试数据满足 $n \le 5 \times 10^4$；

$100\%$ 的测试数据满足 $n \le 10^6$；