Submedians (Easy Version)

The trick is to maximize the upper end of a subarray's median interval.

For a sorted subarray of length $m$:

• if $m$ is odd, there is one median;
• if $m$ is even, every integer between the two middle values is a median.

So the maximum median value contributed by a subarray is its upper middle value. Therefore, the answer is:

the maximum possible upper median among all subarrays of length at least $k$.

Once we can test whether some valid subarray has upper median at least $x$, we can binary search the answer.

Checking a fixed value $x$

For each element, define:

$$b_i = \begin{cases} +1 & a_i \ge x \\ -1 & a_i < x \end{cases}$$

Take any subarray. Let:

• $G$ be the number of elements $\ge x$,
• $L$ be the number of elements $< x$.

The transformed sum of the subarray is:

$$G-L$$

The upper median of this subarray is at least $x$ exactly when at least half of the subarray is $\ge x$.

That condition is:

$$G \ge L$$

which is the same as:

$$G-L \ge 0$$

So for fixed $x$, the whole problem becomes:

Is there a subarray of length at least $k$ whose transformed sum is nonnegative?

Nice. The median monster just turned into prefix sums. Love when Codeforces briefly stops being evil.

Prefix-sum check

Let:

$$pref[0]=0$$

and

$$pref[i]=b_1+b_2+\cdots+b_i$$

The transformed sum of subarray $(l,r)$ is:

$$pref[r]-pref[l-1]$$

We need:

$$r-l+1 \ge k$$

If we set $j=l-1$, then this means:

$$j \le r-k$$

For each right endpoint $r$, we want to know whether there is some valid prefix index $j$ such that:

$$pref[r]-pref[j] \ge 0$$

That is easiest if we maintain the smallest prefix value among all valid $j$:

$$\min_{0 \le j \le r-k} pref[j]$$

Then candidate $x$ works if for some $r$:

$$pref[r]-\min_{0 \le j \le r-k} pref[j] \ge 0$$

When this happens, if the minimum prefix was at index $j$, the witness subarray is:

$$(j+1, r)$$

Binary search

If a threshold $x$ works, then every smaller threshold also works. Lowering $x$ only changes some $-1$ values into $+1$ values, so subarray sums cannot get worse.

So the predicate is monotonic:

$$\text{works}(x) \Rightarrow \text{works}(x-1)$$

Binary search the largest working $x$ from $1$ to $n$.

After finding the answer $v$, run the check once more for $v$ and output its stored subarray.

Why is $v$ itself actually a median of that subarray, not just some threshold that passed? Because the check proves this subarray has upper median at least $v$. But $v$ is the largest threshold that works globally, so no valid subarray can have upper median at least $v+1$. Therefore this subarray's upper median is exactly $v$, and $v$ is definitely inside its median interval.

Complexity

Each check is $O(n)$.

Binary search does $O(\log n)$ checks.

Total per test case:

$$O(n \log n)$$

Across all test cases:

$$O\left(\sum n \log n\right)$$

with $\sum n \le 300000$, easily fine.