We Be Flipping (Easy Version)

Key Observation

The absolute values never change. Only signs flip. Therefore every final array has sum at least

$$-\sum_{i=1}^{n} |a_i|,$$

because each term is either $+|a_i|$ or $-|a_i|$. So if we can make every number negative, we are done. That is the best possible sum, full stop.

Greedy From Right To Left

Operation $i$ flips exactly the prefix $1,2,\dots,i$.

That means operation $i$ does not touch positions $i+1,\dots,n$. So we can safely finalize the array from right to left.

When we are at position $i$:

• if the current value $a_i$ is already negative, leave it alone;
• if the current value $a_i$ is positive, operation $i$ is legal, and after applying it, $a_i$ becomes negative.

After this, future operations only use smaller indices, so position $i$ will never be touched again.

Avoiding Actual Prefix Flips

Naively flipping prefixes would be $O(n^2)$, which is dumb and deserves jail time.

Instead, keep one parity variable $flip$:

$$flip = 0 \text{ means current signs are unchanged},$$ $$flip = 1 \text{ means current signs are inverted}.$$

For original value $a_i$, its current positivity is:

$$(a_i > 0) \oplus flip.$$

If it is currently positive, append $i$ to the answer and toggle $flip$.

Why does toggling one variable work? While scanning right to left, every operation we have already performed was on an index larger than the current one, so it flipped the current position. Every future position also lies inside the prefix we just flipped.

Correctness Proof

We prove the invariant: after processing position $i$, every position $j \ge i$ is negative and will never change again.

Before processing anything, the claim is vacuously true for positions to the right of $n$.

Now consider position $i$.

If $a_i$ is currently negative, we do nothing, so it is finalized as negative.

If $a_i$ is currently positive, operation $i$ is allowed by the statement. It flips $a_i$, making it negative. It may flip positions $1,\dots,i-1$, but those are not finalized yet. It does not affect positions $i+1,\dots,n$, so previously finalized positions remain negative.

Thus the invariant holds.

At the end, all positions are negative, so the final sum is

$$-\sum_{i=1}^{n}|a_i|,$$

which is the smallest possible sum. Therefore the produced sequence is optimal.

Complexity

We scan the array once and output at most one operation per index.

$$O(n) \text{ per test case}, \qquad O(n) \text{ memory}.$$