Ultimate Value

Let

$$S = a_1-a_2+a_3-a_4+\cdots+(-1)^{n+1}a_n.$$

That is the value of the array before any swaps, ignoring cost.

The important game observation is brutal but simple: the game ends after at most Alice's first meaningful move under optimal play.

Why? Alice moves first. If she ends immediately, the answer is $S$. If she swaps something, then Bob gets the next turn and can end the game immediately. Since Bob minimizes the final value, Alice cannot rely on Bob generously making extra moves that help her. So Alice's job is just:

$$\text{answer}=S+\max(0, \text{best gain from one swap}).$$

The rest is figuring out that best gain.

Effect of a swap

Let the sign at index $i$ be:

$$\sigma_i = \begin{cases} +1 & i\text{ odd},\\ -1 & i\text{ even}. \end{cases}$$

Before swapping indices $i,j$, their contribution is

$$\sigma_i a_i + \sigma_j a_j.$$

After swapping, it becomes

$$\sigma_i a_j + \sigma_j a_i.$$

So the change in alternating sum is

$$(\sigma_i a_j + \sigma_j a_i) - (\sigma_i a_i + \sigma_j a_j).$$

The swap also adds cost $|i-j|$.

We only consider $i<j$, so the cost is $j-i$.

Same parity swaps

If $i$ and $j$ have the same parity, then $\sigma_i=\sigma_j$. Swapping them does not change $S$ at all. The gain is just:

$$j-i.$$

Alice wants the largest distance between two indices of the same parity.

• If $n$ is odd, indices $1$ and $n$ are both odd, so gain is $n-1$.
• If $n$ is even, the best same-parity distance is $n-2$.

For $n=1$, this is $0$.

So initialize:

$$\text{best}=\begin{cases} 0 & n=1,\\ n-1 & n\text{ odd},\\ n-2 & n\text{ even}. \end{cases}$$

Different parity swaps

Now suppose $i<j$ and the parities differ.

Case 1: $i$ odd, $j$ even.

Before:

$$+a_i-a_j$$

After:

$$+a_j-a_i$$

Change in alternating sum:

$$2(a_j-a_i).$$

Including cost, gain is:

$$(j-i)+2(a_j-a_i)$$

or equivalently:

$$(j+2a_j)+(-i-2a_i).$$

So while scanning left to right, for an even index $j$, we want the maximum previous odd value of:

$$-i-2a_i.$$

Case 2: $i$ even, $j$ odd.

Before:

$$-a_i+a_j$$

After:

$$-a_j+a_i$$

Change in alternating sum:

$$2(a_i-a_j).$$

Including cost, gain is:

$$(j-i)+2(a_i-a_j)$$

or:

$$(j-2a_j)+(-i+2a_i).$$

So for an odd index $j$, we want the maximum previous even value of:

$$-i+2a_i.$$

That gives an $O(n)$ scan:

• Maintain bestOdd = max(-i - 2*a[i]) over previous odd indices.
• Maintain bestEven = max(-i + 2*a[i]) over previous even indices.
• At even $j$, candidate gain is $j+2a_j+bestOdd$.
• At odd $j$, candidate gain is $j-2a_j+bestEven$.

Take the maximum of these and the same-parity gain.

Finally print:

$$S+\text{best}.$$

The values fit in long long: $S$ is at most about $2\cdot10^{14}$ in magnitude, and gains are also around that size. int would explode. Not dramatically, just enough to ruin your day.