Deque Process

The annoying part of the statement is that it talks about five numbers. Translate it into signs and it becomes much less dramatic.

For each adjacent pair in the final array $q$, write:

• + if $q_i < q_{i+1}$
• - if $q_i > q_{i+1}$

Since $q$ is made from a permutation, equality never happens. A bad segment of length $5$ is exactly four equal signs in a row:

• increasing: ++++
• decreasing: ----

So our real job is: choose from the deque so the sign string has no run of length $4$.

Pair Trick

Look at the two current ends of the deque. Call them $L$ and $R$.

If $L<R$:

• taking L then R creates an increasing pair
• taking R then L creates a decreasing pair

If $L>R$, the opposite order does the same thing. In general:

• to force an increasing pair, take the smaller end first, then the larger end
• to force a decreasing pair, take the larger end first, then the smaller end

And because both values are ends, after removing the first one, the other one is still an end. No magic, no hidden data structure, just deque physics.

Now do this in pairs:

• pair $0$: make it increasing
• pair $1$: make it decreasing
• pair $2$: make it increasing
• pair $3$: make it decreasing
• and so on

So inside the pairs, the comparison signs alternate:

$$+, -, +, -, \ldots$$

There is also one comparison sign between consecutive pairs. We do not control it directly, and we do not need to.

Why? Around the boundary between pair $k$ and pair $k+1$, the sign pattern looks like:

$$\text{inside pair }k,\quad \text{boundary},\quad \text{inside pair }k+1$$

The inside signs of neighboring pairs are opposite. So locally it is either:

$$+\ ?\ -$$

or

$$-\ ?\ +$$

That unknown middle sign can be whatever it wants. It is trapped between opposite signs, so it cannot help create four equal signs in a row. The longest dangerous streak gets broken constantly. Very rude to monotonic runs, which is exactly what we want.

Odd length

If $n$ is odd, after processing pairs one element remains. Take it from the left. This adds only one final comparison sign. Could that suddenly create four equal signs? No.

The last completed pair already has an internal sign, and the previous completed pair had the opposite internal sign, so near the end there is still a recent forced break. Appending one value cannot produce four equal signs unless the previous three signs were already equal, but our pair construction prevents that kind of unchecked run.

Algorithm

Maintain two pointers $l$ and $r$.

For pair number $k=0,1,2,\ldots$:

• if $k$ is even, create an increasing pair:
  • take the smaller of $p_l,p_r$
  • then take the other end
• if $k$ is odd, create a decreasing pair:
  • take the larger of $p_l,p_r$
  • then take the other end

Record L or R for every taken side.

If one element remains, take it.

The complexity is $O(n)$ per test case, and $O(\sum n)$ overall. The implementation is tiny. Suspiciously tiny, even. But it works because the construction attacks the exact thing that makes an array bad: long runs of identical comparison signs.