最大中位数

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定长度为 $n$ 的整数序列 $a$。在所有长度至少为 $k$ 的连续子数组中，求中位数的最大可能值。

长度为 $x$ 的数组排序后，第 $\left\lfloor\frac{x+1}{2}\right\rfloor$ 小的元素称为其中位数。

输入格式

第一行包含两个整数 $n,k$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示答案。

样例输入 1

5 3
1 2 3 2 1

样例输出 1

2

样例输入 2

4 2
1 2 3 4

样例输出 2

3

数据范围

• $1\le k\le n\le 2\times 10^5$；
• $1\le a_i\le n$。