First or Second

The operation looks annoying because the line changes, but the key is that the order never changes. We only delete things.

So the current line is always the original order with some children missing. At each step, Santa can remove either:

• the current first child, adding its value;
• the current second child, subtracting its value.

The first child acts like a blocker. If you keep them, you can repeatedly delete the next child as the second child. If you finally remove the blocker, the next surviving child becomes the new blocker.

That is basically the whole game. No dark magic, no cursed DP table.

Fix the remaining child

Suppose child $r$ is the one left unassigned at the end.

First, consider every child after $r$.

Once child $r$ becomes the first child in line, we cannot remove them, because they are supposed to remain. The only way to keep going is to remove the child after them as the second child. Then the next child after that is second, and so on.

Therefore every child $i>r$ is forced to be removed as the second child, contributing:

$$-a_i$$

So the suffix after $r$ contributes:

$$-\sum_{i=r+1}^{n} a_i$$

Now look before $r$.

Child $1$ is special. Initially, there is no child before child $1$, so child $1$ can never be removed as the second child. It has only two possibilities:

• if $r=1$, child $1$ remains and contributes $0$;
• if $r>1$, child $1$ must eventually be removed as the first child, contributing $+a_1$.

For the middle children $2,3,\ldots,r-1$, we have freedom. Each such child can be made either:

• positive, by letting it become first and removing it as the first child;
• negative, by keeping some earlier child in front and removing it as the second child.

So for each $2 \le i < r$, we simply choose the better of $+a_i$ and $-a_i$, which is:

$$|a_i|$$

This is the part where a fake complicated DP gets absolutely bodied by just understanding the process.

Value for a fixed remaining position

If $r=1$, child $1$ remains, and every other child is removed as second:

$$value(1) = -\sum_{i=2}^{n} a_i$$

If $r>1$, then:

• child $1$ contributes $+a_1$;
• children $2$ through $r-1$ contribute their absolute values;
• child $r$ contributes $0$;
• children after $r$ contribute negative values.

So:

$$value(r)=a_1+\sum_{i=2}^{r-1}|a_i|-\sum_{i=r+1}^{n}a_i$$

The answer is:

$$\max_{1\le r\le n} value(r)$$

Why the freedom before $r$ is real

Take any child $i$ with $2 \le i < r$.

If we want child $i$ to be negative, keep the current first child alive and remove $i$ as the second child.

If we want child $i$ to be positive, first remove the current first child. Then child $i$ becomes the first child, and later we remove it as first.

This lets us choose the sign of every middle child independently. The only exception is child $1$, because nothing can stand before it.

Implementation

Precompute suffix sums:

$$suf[i]=a_i+a_{i+1}+\cdots+a_n$$

Then:

• $value(1)=-suf[2]$;
• for $r>1$, maintain $prefAbs=\sum_{i=2}^{r-1}|a_i|$ while scanning $r$ from left to right.

For each $r$:

$$a_1 + prefAbs - suf[r+1]$$

Update the answer, then add $|a_r|$ to prefAbs for the next position.

Use long long, because values can reach around $2\cdot 10^{14}$, and int would explode like it got reviewed by a compiler with trust issues.

Complexity: $O(n)$ per test case, and $O(n)$ memory. You can also do it with less memory, but suffix sums are clean and boring, which is exactly what we want here.