给定一个长度为 $$$n$$$ 的数组 $$$a$$$。查找长度至少为 $$$k$$$ 且中位数最大的子数组 $$$a[l..r]$$$。
长度为 $$$n$$$ 的数组中的中位数是按非降序对元素进行排序后占据位置号 $$$\lfloor \frac{n + 1}{2} \rfloor$$$ 的元素。例如:$$$中位数([1, 2, 3, 4]) = 2$$$, $$$中位数([3, 2, 1]) = 2$$$, $$$中位数([2, 1, 2, 1]) = 1$$$。
子数组 $$$a[l..r]$$$ 是数组 $$$a$$$ 的连续部分,i。 e.数组 $$$a_l,a_{l+1},\ldots,a_r$$$ 对于某些 $$$1 \leq l \leq r \leq n$$$,其长度为 $$$r - l + 1$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$)。
输出
输出一个整数 $$$m$$$ — 您可以获得的最大中位数。
示例
输入 #1
5 3 1 2 3 2 1
输出 #1
2
输入 #2
4 2 1 2 3 4
输出 #2
3
注意
在第一个示例中,所有可能的子数组为 $$$[1..3]$$$、$$$[1..4]$$$、$$$[1..5]$$$、$$$[2..4]$$$、$$$[2..5]$$$ 和 $$$[3..5]$$$,所有子数组的中位数为 $$$2$$$,因此最大可能的中位数也是$$$2$$$。
在第二个示例中 $$$median([3..4]) = 3$$$。