Maximise Sum

The operation has one very loud consequence:

If we choose $(i,j)$, then $a_j$ becomes $0$, so every prefix ending at $j$ or later contributes $0$.

So the score after the operation is only

$$\sum_{k=1}^{j-1} \min(b_1,\dots,b_k),$$

where $b_i=a_i+a_j$, $b_j=0$, and all other values stay the same.

Let

$$mn[k]=\min(a_1,\dots,a_k),\qquad pref[k]=\sum_{t=1}^k mn[t].$$

The no-operation score is $pref[n]$, and it only matters for $x=0$.

Useful left endpoints

If $i$ is not a strict prefix minimum, then some earlier element is already $\le a_i$. Increasing $a_i$ cannot improve any prefix minimum. It is dead weight.

So we only need positions satisfying

$$a_i < mn[i-1].$$

For such an $i$, after adding $a_j$, the new active minimum at position $i$ is

$$cur=\min(a_i+a_j, mn[i-1]).$$

It is capped by $mn[i-1]$, because prefixes ending at $i$ still include everything before $i$.

Useful right endpoints

If $j$ is not a strict suffix maximum, there is some later $j'>j$ with $a_{j'}\ge a_j$.

Using $j'$ instead is never worse:

• it adds at least as much to $a_i$,
• it zeroes out a later index,
• it has larger cost.

So every optimal operation can be replaced by one where $j$ is a strict suffix maximum.

Scoring one pair

Fix a strict prefix minimum $i$ and a strict suffix maximum $j>i$.

Prefixes before $i$ are unchanged, contributing

$$pref[i-1].$$

Now define

$$cur=\min(a_i+a_j,mn[i-1]).$$

Find the first position after $i$ whose value is at most $cur$:

$$pos=\min\{p>i:a_p\le cur\}.$$

If it does not exist, use a sentinel $n+1$.

From $i$ through

$$upto=\min(j-1,pos-1),$$

the prefix minimum is exactly $cur$, so this block contributes

$$cur\cdot(upto-i+1).$$

So initially:

$$val=pref[i-1]+cur\cdot(upto-i+1).$$

If $upto+1\ge j$, we are done.

Otherwise, the raised $a_i$ stopped being the minimum before $j$. We need the rest of the prefix-minimum sum until $j-1$.

Let $nextPref[i]$ be the next strict prefix-minimum position after $i$.

For indices after $i$ but before $nextPref[i]$, the old blocker was $a_i$. Once $a_i$ is no longer the minimum, the answer becomes the second prefix minimum: the smallest value in the prefix excluding this current strict prefix-minimum blocker.

Precompute:

$$sec[k]=\text{second prefix minimum of }a_1,\dots,a_k.$$

Also store its prefix sum $prefSec$.

Let

$$split=\min(nextPref[i],j).$$

Then the remaining part is:

$$\sum_{k=upto+1}^{split-1} sec[k] + \sum_{k=split}^{j-1} mn[k].$$

Using prefix sums:

$$val += prefSec[split-1]-prefSec[upto] + pref[j-1]-pref[split-1].$$

That gives the exact value of operation $(i,j)$.

Finding pos

Scan $i$ from right to left and maintain a monotone stack of suffix-minimum breakpoints. The stack has increasing values, so for a given $cur$ we binary search the first position to the right with value $\le cur$.

Each tested pair is therefore scored in $O(\log n)$.

Why the pair count is linear

For a fixed strict prefix minimum $i$, enumerate strict suffix maxima $j$ from right to left. Their values strictly increase.

Stop once

$$a_i+a_j\ge mn[i-1].$$

After that, $cur$ is capped at $mn[i-1]$. Any further suffix maximum is to the left, gives the same capped $cur$, and deletes earlier, so it is dominated by the pair where we stopped.

For $i>1$, the number of uncapped suffix maxima tested is at most

$$mn[i-1]-a_i,$$

plus one capped candidate. Across all strict prefix minima, these drops telescope to at most $n$, since all values are in $[0,n]$. For $i=1$, we may scan all suffix maxima once. Total tested pairs are $O(n)$.

For every tested pair, update

$$best[j-i]=\max(best[j-i],val).$$

Finally, the answer for required cost at least $x$ is

$$\max_{d\ge x} best[d],$$

so suffix-max the best array. Set best[0]=pref[n] first to include doing nothing.

Complexity: $O(n\log n)$ per test case from the stack binary searches, with total $n\le 10^6$. Memory is $O(n)$.