Even Larger

Define a signed version of the array:

$$b_i = \begin{cases} a_i, & i \text{ is even},\\ -a_i, & i \text{ is odd}. \end{cases}$$

The condition says: every subarray of length at least $2$ must have signed sum at least $0$.

So even indices are the good guys and odd indices are the debt. Decreasing an even-indexed value would decrease a positive term, making constraints harder while also costing an operation. That is paying money to punch yourself in the face. In an optimal solution, we only decrease odd-indexed elements.

Why local checks are enough

Suppose every subarray of length $2$ and $3$ has nonnegative signed sum.

Any longer subarray can be split into consecutive blocks of length $2$ and possibly one block of length $3$:

• length $4 = 2+2$;
• length $5 = 2+3$;
• length $6 = 2+2+2$;
• and so on.

Each block has nonnegative signed sum, so the whole subarray also has nonnegative signed sum. Therefore, checking all subarrays is unnecessary; length $2$ and length $3$ already force everything.

Now simplify those local constraints.

Look at an even index $i$. Its odd neighbors are $i-1$ and $i+1$, if they exist. The length-$3$ subarray

$$[i-1,i,i+1]$$

requires

$$a_i \ge a_{i-1}+a_{i+1}.$$

At the boundary, a missing neighbor just contributes $0$, so the same rule also covers length-$2$ edge cases:

$$a_{i-1}+a_{i+1}\le a_i.$$

This one rule for every even index is enough. Since all values are nonnegative, it also implies the adjacent length-$2$ constraints. For example, if $a_{i-1}+a_{i+1}\le a_i$, then certainly $a_{i-1}\le a_i$ and $a_{i+1}\le a_i$.

So the problem becomes:

• keep even positions unchanged;
• decrease odd positions as little as possible;
• for every even index $i$, enforce

$$a_{i-1}+a_{i+1}\le a_i.$$

Greedy choice

Process even indices from left to right.

At an even index $i$, suppose currently

$$a_{i-1}+a_{i+1}>a_i.$$

Let

$$\text{extra}=a_{i-1}+a_{i+1}-a_i.$$

At least extra operations are unavoidable, because the sum of these two odd neighbors must go down by that much.

Which neighbor should we decrease?

Decrease the right neighbor first.

Why? The left neighbor $a_{i-1}$ will not appear in any future even-index constraint. It was only relevant to the current even index and maybe previous ones. Decreasing it now cannot help the future.

The right neighbor $a_{i+1}$ will appear in the next constraint around even index $i+2$. Making it smaller can only help later. So spending deletions on the right side first is never worse.

If the right neighbor is not large enough to absorb all extra, delete the rest from the left neighbor.

This fixes the current constraint using exactly the minimum forced number of operations, and it makes future constraints as easy as possible. Repeating this left to right gives the global minimum.

Algorithm

For every even index $i=2,4,6,\dots$:

1. Compute extra = a[i-1] + a[i+1] - a[i], with $a_{n+1}=0$.
2. If extra <= 0, this even index is already fine.
3. Otherwise, decrease $a_{i+1}$ by as much of extra as possible.
4. If some extra remains, decrease $a_{i-1}$ by the rest.
5. Add all decreases to the answer.

All arithmetic must use long long, since the answer can be much larger than $10^9$.

Complexity

Each element is touched only a constant number of times, so the complexity is

$$O(n)$$

per test case, and $O(\sum n)$ overall.