We Be Flipping (Hard Version)

Encode the signs

Let

$$X=\sum_{i=1}^{n} [a_i>0]2^{i-1}.$$

So bit $i$ tells whether $a_i$ is currently positive. If we perform operation $i$, bit $i$ must be $1$, and bits $1,2,\dots,i$ are toggled:

$$X' = X \oplus (2^i-1).$$

Look at the lower $i$ bits as a number $L$. Since bit $i$ is set,

$$2^{i-1} \le L < 2^i.$$

After toggling those bits, the new lower part is

$$L' = 2^i-1-L < L.$$

Higher bits do not change, so the whole mask strictly decreases. That is the key: every valid final mask $Y$ must satisfy

$$Y \le X.$$

No vibes, no magic, just binary being annoyingly useful.

Optimize the final mask

For a final mask $Y$, the final sum is

$$\sum_{i=1}^{n} (2Y_i-1)|a_i| = -\sum_{i=1}^{n}|a_i| + 2\sum_{i:Y_i=1}|a_i|.$$

The first term is constant, so we only need to maximize

$$W(Y)=\sum_{i:Y_i=1}|a_i|.$$

among all $Y\le X$.

If $Y=X$, the score is simply the weight of initially positive elements.

Otherwise, let $p$ be the highest bit where $X$ and $Y$ differ. Since $Y<X$, we must have

$$X_p=1,\qquad Y_p=0,$$

and all bits above $p$ are equal to $X$. Bits below $p$ are completely free from the numeric constraint, and every weight $|a_i|$ is positive, so the best choice is to set all of them to $1$.

Therefore, every optimal candidate is one of these:

$$Y=X,$$

or for some positive position $p$:

$$Y_i= \begin{cases} X_i, & i>p,\\ 0, & i=p,\\ 1, & i<p. \end{cases}$$

The score for choosing $p$ is

$$V_p=\sum_{i=1}^{p-1}|a_i|+\sum_{i=p+1}^{n}[a_i>0]|a_i|.$$

Compute prefix sums of $|a_i|$ and suffix sums of initially-positive $|a_i|$, then try all $p$ with $a_p>0$.

Construct the operations

If the best choice is $Y=X$, output no operations.

Otherwise, suppose the chosen position is $p$. We need the final state to have:

• positions $i>p$ unchanged,
• position $p$ negative,
• positions $i<p$ positive.

The final operation will be $p$. Since $a_p$ is initially positive and operations below $p$ never touch it, that operation will be valid.

Before flipping $p$, we want positions $1,2,\dots,p-1$ to all be negative, because operation $p$ will flip them all to positive.

To make prefix $p-1$ all negative, scan downward from $p-1$ to $1$. Maintain a parity $flip$ telling whether previous larger operations have toggled the current bit. If the current bit is positive, operate there; this makes it negative and toggles all lower bits.

This uses at most one operation per index, plus the final operation at $p$, so

$$k\le p\le n.$$

Correctness

Every operation strictly decreases the sign mask $X$, so no valid sequence can end at a mask greater than the initial one. Thus any achievable final answer is bounded by the best weighted mask $Y\le X$.

The optimization step checks exactly the only masks that can be optimal under $Y\le X$: either $Y=X$, or at the highest differing bit $p$, we turn that bit off and set every lower bit on.

The construction produces exactly the selected mask: first it makes all bits below $p$ equal to $0$, then operation $p$ flips them to $1$ and flips bit $p$ to $0$, while leaving all higher bits unchanged. Every operation is performed only when its current bit is $1$, so the sequence is valid.

Therefore the produced sequence maximizes the final sum.

Complexity

For each test case, everything is linear:

$$O(n)$$

time and

$$O(n)$$

memory. Across all test cases this is $O(\sum n)$.