Make it Zigzag

The annoying-looking part is operation 1 using the current prefix max. The trick is that we can do all useful increases first, before decreasing anything. So operation order is not a curse; it is basically free peak inflation.

Prefix max cap

Define

$M_i = \max(a_1, a_2, ..., a_i)$.

Claim: position $i$ can never become larger than $M_i$.

Initially this is true. Decreasing obviously keeps it true. If we apply operation 1 at position $i$, the new value becomes the current maximum among positions $1..i$. But every one of those positions is still at most its own original prefix maximum, and all of those are at most $M_i$. So the result is also at most $M_i$.

So $M_i$ is a hard ceiling for position $i$.

Who needs to be changed?

The final pattern is

$b_1 < b_2 > b_3 < b_4 > ...$

Even positions are peaks. Bigger peaks are always good, because they only need to be greater than their neighbors. Since operation 1 is free, we should make every even position as large as possible: set even position $i$ to $M_i$.

Odd positions are valleys. They may need to be decreased.

For odd $i = 1$, we only need

$b_1 < b_2$.

Since $b_2 \le M_2$, we must have

$b_1 \le M_2 - 1$.

For odd $i > 1$, the left neighbor $i-1$ is even, so

$b_i < b_{i-1}$.

And because $b_{i-1} \le M_{i-1}$,

$b_i \le M_{i-1} - 1$.

If $i$ also has a right neighbor, that right even peak has cap $M_{i+1}$. Since prefix maxima never decrease, $M_{i+1} \ge M_{i-1}$, so the left peak is the tighter or equal bound. Nice. No DP, no drama.

Cost for one odd position

Let the largest allowed final value for odd position $i$ be:

• $M_2 - 1$, if $i=1$;
• $M_{i-1} - 1$, otherwise.

If $a_i$ is already at most this value, cost is $0$.

Otherwise, we must decrease it to that value, costing

$a_i - limit$.

So we add

$\max(0, a_i - limit)$

over all odd positions.

Why this is actually achievable

Do this construction:

1. Before any decreases, apply operation 1 to every even index. Then each even index $i$ becomes $M_i$.
2. For every odd index, decrease it only if it is above its limit.

Now every odd position is strictly smaller than the even peak to its left, or for $i=1$, strictly smaller than position $2$. If it also has a right even neighbor, that right peak is at least as large as the left peak because prefix maxima are nondecreasing.

So the array is awesome, and the cost exactly matches the lower bound. That means it is optimal.

Complexity

Compute prefix maxima once and scan odd indices.

Time: $O(n)$ per test case.

Memory: $O(n)$, or $O(1)$ extra if streamed carefully. The simple array version is already totally fine.