CF2128E2 Submedians (Hard Version)

考虑一个很直觉的东西，可行的中位数一定是连续的。具体来说，你将一个区间左右端点扩展，中位数一定只会有 \(+1, -1\) 的变化，因此覆盖到的区间一定是连续的。

我们找出可以的最小的中位数，和最大的中位数，类似莫队去扩展，此时只需要支持加入删除和动态维护中位数即可。

如果此时向左向右扩展，可以保证的是区间长度 \(\ge k\) 时，其中位数一定大于最小的中位数，否则最小的中位数就不是它了。