Minimise Sum

Let

$m_k=\min(a_1,a_2,\ldots,a_k).$

The value we care about is

$m_1+m_2+\cdots+m_n.$

The operation chooses $i<j$, does $a_i:=a_i+a_j$, then sets $a_j=0$.

The second part is huge: once $a_j=0$, every prefix containing position $j$ has minimum $0$. So after the operation, all terms from $j$ onward contribute nothing. Nice.

The only possible downside is that $a_i$ got increased, so some prefix minimums before $j$ might become larger. Since all values are nonnegative, $a_i+a_j\ge a_i$, so this increase can never help. It either does nothing or makes things worse.

When is an index safe?

Suppose we choose some index $i>1$. Let

$p=\min(a_1,\ldots,a_{i-1}).$

If $a_i\ge p$, then $a_i$ was not responsible for lowering the prefix minimum. There is already an earlier element at most as small as it.

So increasing $a_i$ changes nothing for prefix minimums at positions $i,i+1,\ldots$ before the zero. The earlier smaller element still wins.

So index $i$ is safe exactly when

$a_i\ge \min(a_1,\ldots,a_{i-1}).$

If such a safe index $i<n$ exists, we should choose $j=i+1$. Why wait longer? Choosing $j=i+1$ makes everything after $i$ become $0$ as early as possible, and increasing $a_i$ does not hurt. The resulting value is simply

$m_1+m_2+\cdots+m_i.$

Since prefix minimums are nonnegative, these prefix sums never decrease, so the earliest safe usable index gives the best such move.

What if we use an unsafe index?

Unsafe means $a_i$ is strictly smaller than everything before it. It is a new prefix minimum.

If you increase such an element, you may destroy the very reason it was useful. That is bad. We need to show we do not need to try every unsafe operation.

There is always the simple operation $(1,2)$. It gives value

$a_1+a_2,$

because position $2$ becomes $0$, so everything after it contributes $0$.

Now consider any unsafe choice before the first safe index. The array has been strictly decreasing so far, so just the first two prefix-minimum terms already sum to $a_1+a_2$. Delaying the zero cannot beat that; it only keeps more nonnegative terms alive.

So the only candidates are:

1. do nothing,
2. perform $(1,2)$, giving $a_1+a_2$,
3. for any safe $i<n$, perform $(i,i+1)$, giving the original prefix-minimum sum up to $i$.

We scan left to right while maintaining the current prefix minimum and prefix-minimum sum. Whenever $a_i$ is at least the previous prefix minimum and $i<n$, index $i$ is safe, so we minimize the answer with the prefix sum through $i$.

That is $O(n)$ per test case, with total $O(\sum n)$.