Remove at the lowest cost

Key Observation

Think about one fixed element $i$. It is removed exactly once. At that moment it is adjacent to some element $j$ with $a_j \ge a_i$, and the paid cost is $\min(c_i,c_j)$.

The important question is: which $j$ can ever be that neighbor?

Suppose $j<i$. For $j$ and $i$ to become adjacent while both are still alive, every element between them must already be gone. If, while moving left from $i$, there is a position between them with value greater than $a_j$, then that bigger element blocks $j$ from being the element that kills $i$. So $j$ must be a record maximum while scanning left from $i$.

Those record maxima are exactly this chain:

• take the nearest index to the left with value $\ge a_i$;
• from there, take its nearest index to the left with value $\ge$ its value;
• repeat.

The right side is symmetric.

So for every index $i$, define:

• $L_i$ = all indices on that left nearest-greater-or-equal chain;
• $R_i$ = all indices on that right nearest-greater-or-equal chain.

Then the cheapest possible charge for deleting $i$ is

$$w_i=\min\left(c_i,\min_{j\in L_i} c_j,\min_{j\in R_i} c_j\right).$$

The $c_i$ part is not optional. If $i$ itself is cheap, then deleting it next to any valid bigger element costs $c_i$.

Which element survives?

The last remaining element must have maximum value in the whole array. A non-maximum can never delete a global maximum, because smaller values lose.

If there is a unique global maximum at index $r$, it must survive, so the static answer is

$$\sum_{i\ne r} w_i.$$

If there are multiple global maxima, exactly one of them survives. Every global maximum can delete another global maximum after the lower stuff between them is cleared, so we choose the survivor that saves the largest charge:

$$\sum_i w_i-\max_{a_i=M} w_i,$$

where $M=\max a_i$.

That is the whole static problem. No interval DP circus. Thank god.

Computing the chains

Use a monotonic stack.

For the left chain, scan left to right. Before processing $i$, pop all indices with value strictly smaller than $a_i$. The stack top, if it exists, is the nearest previous index with value at least $a_i$.

If that parent is $p$, then the whole left chain of $i$ is just $p$ plus the left chain of $p$. Therefore:

$$\text{leftCost}[i]=\min(c_p,\text{leftCost}[p]).$$

Do the same scan from right to left for $\text{rightCost}$.

Now handle zeroing

Let $\operatorname{pos}[x]$ be the query number when index $x$ becomes zero.

For an index $i$, its contribution $w_i$ becomes $0$ as soon as any of these indices is zeroed:

• $i$ itself;
• anything on $L_i$;
• anything on $R_i$.

So define a death time:

$$t_i=\min\left(\operatorname{pos}[i],\min_{j\in L_i}\operatorname{pos}[j],\min_{j\in R_i}\operatorname{pos}[j]\right).$$

For query count $q$, contribution $w_i$ is still alive iff $t_i>q$.

We compute the chain minimum query times using the exact same stack DP as costs:

$$\text{leftTime}[i]=\min(\operatorname{pos}[p],\text{leftTime}[p]).$$

Then sweep $q=0,1,\dots,n$:

• keep total = sum of all currently alive $w_i$ contributions;
• subtract all contributions whose death time just arrived;
• if there are multiple global maxima, subtract the largest currently alive $w_i$ among them, because one max survives.

A max-heap over global maxima handles that last part.

Complexity

Each test case is $O(n\log n)$ because of the heap. The stack work is linear. The memory usage is $O(n)$.