题意

定义合法区间为区间长度大于等于L的区间，找到所有合法区间内最大的中位数。

题解

如果去掉区间限制，那最大中位数就是只取最大的数，这方面好像没什么可优化的点。我们转成另一个问题，判断是否存在一个合法区间的最大中位数大于等于$x$。

如何判定这个问题？ 一个长度为$L$的区间内，假设小于$x$的数一共有$y$个，那是否应该为 $y \leq \lceil \frac{L}{2} \rceil$，就可以说明中位数大于等于$x$。

所以前面的问题变成了如何判定一个区间，大于等于$x$的数的数量 $\geq$ 小于它的数的数量。我们把大于等于$x$的数写成$1$，其它写成$-1$。就变成了 $1的数量 \geq -1的数量$。问题变成了找到一个区间的和大于等于 $0$。

如何找到一个合法区间的和大于等于$0$？

设前缀和数组为$Sum$即判断是否存在$[l,r]$使得$Sum_r - Sum_{l-1} \geq 0$且$r - l + 1 \geq L$。我们枚举 $r$，就知道 $l$ 的合法区间是一个前缀（即$[1, \dots, r + 1 - L]$），那就是要找这个前缀里找到$S[l-1]$的值最小。那就可以使得$Sum_r - Sum_{l-1}$最大。判定它是否大于$0$。

假设我们知道 $f(x)$ 表示合法区间$是否$存在中位数大于等于 $x$。那我们只要找到一个最大$f(x) == true$，可以注意到定义和前面，我们发现随着$x$增大，这个条件越不容易满足。所以是满足单调性的。那只需要二分$x$即可。