Hints: Median Deletion

You delete the median (second smallest) among three consecutive elements—unlike problem A, where you deleted min or max. For $n=1$, what is the answer for each position?

Answer to Hint 1: No operation is possible, so every answer is $1$.

For $n \ge 2$, length $1$ is impossible (you always remove one element from a triple, so at least two remain until you stop). What are the possible minimal lengths in this problem?

Answer to Hint 2: The minimum length containing a fixed value is always between $2$ and $5$ in the intended solution (and never below $2$). The global minimum and maximum values $1$ and $n$ behave more simply than middle values.

Try the sample: min and max often admit length $2$; some elements require $3$, $4$, or $5$ depending on the relative order of other extrema.

Answer to Hint 3: Let $\text{pos}(v)$ be the index of value $v$. The positions of $0$ and $n-1$ in value-indexed form (after subtracting $1$ from inputs) matter: whether the minimum lies left or right of a position $i$, and whether the maximum lies left or right, splits cases.

Build range min/max structures over the value array $a[\cdot]$ (not the position array) to query smallest/largest values in a suffix or prefix of indices.

Answer to Hint 4: For a candidate index $i$, you often compare:

• the nearest larger/smaller values on the left and right of $i$ in terms of values $a[i]$,

• positions of global min $0$ and max $n-1$ relative to $i$,

• and whether certain quadruples of “witness” positions interleave or nest.

These determine if you can eliminate everything except your target with two deletions, or whether you need three or more rounds of median removal.

Answer to Hint 5: The implementation follows a case analysis on the order of $\text{pos}(0)$, $\text{pos}(n-1)$, and $i$, plus RMQ queries on the left and right intervals for the smallest value $< a[i]$ and largest value $> a[i]$.

When $\text{pos}(0)$ and $\text{pos}(n-1)$ lie on opposite sides of $i$, one regime applies; when both lie on one side, another regime with suffix/prefix extrema applies.

Answer to Hint 6: The reference solution runs the same logic on $a$ and on the reversed array, then reverses the answer array, and takes a coordinate-wise minimum of the two runs—symmetry covers patterns that appear only when scanning from the other end.

After both passes, output the per-index minima as the final answers.

Answer to Hint 7: Use a sparse table (or segment tree) for range min and range max on the value-at-index array; each query is $O(\log n)$ or $O(1)$, so total $O(n \log n)$ or $O(n)$ per test case.

Testing small $n$ by hand on samples helps validate the case split before coding every branch.