光玉

时间限制：1000MS 512MB

题目描述

在这个被漫天积雪覆盖、时间近乎停滞的幻想世界中，只有一名少女和一台由废铁拼凑而成的机器人。由于世界的力量正在衰减，少女变得越来越虚弱。机器人决定带她穿过荒芜的雪原，寻找那些散落在远方的心愿之光------"光玉"，以此来积蓄引发奇迹的能量。

雪原由编号为 $1$ 至 $N$ 的 $N$ 个残骸点组成。每个点都漂浮着一颗光玉，其纯净度为 $a_i$。机器人带着少女从编号为 $0$ 的起点出发（位置 $0$ 处没有光玉），目标是到达编号为 $N$ 的终点残骸点。

机器人动力核心的跳跃能力有限，它每次只能向前方跳跃 $1$ 到 $K$ 个格子。换言之，若当前位于位置 $i$ ($0 \le i < N$)，下次可跳跃至位置 $j \in [i+1, \min(i+K, N)]$。

每当机器人落在一个残骸点时，就会收集到该点的光玉。当他们最终到达终点 $N$ 时，收集到的所有光玉将凝聚在一起。根据"奇迹协议"，这组光玉序列的中位数纯净度越高，引发奇迹拯救少女的可能性就越大。

请计算，在所有可能的路径中，机器人能收集到的光玉序列的最大中位数是多少？

中位数定义：若收集的光玉序列长度为 $L$，将其升序排序后，第 $\lfloor \frac{L+1}{2} \rfloor$ 个位置的数即为中位数。

输入描述

第一行包含两个整数 $N, K$ ($1 \le N \le 2 \times 10^5, 1 \le K \le N$)，分别表示残骸点总数和机器人的最大跳跃距离。第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$ ($0 \le a_i \le 10^9$)，分别表示每个残骸点光玉的纯净度。

输出描述

输出一个整数，表示可能的最大中位数。

输入样例

5 2
1 2 3 4 5

输出样例

4

输入样例

6 3
100 0 0 0 200 200

输出样例

200

输入样例

5 2
2 3 4 5 1

输出样例

3