Prefix Max

Let $M = \max(a_1, a_2, \ldots, a_n)$.

For any array order, each prefix maximum is at most $M$, because no element in the array is larger than the global maximum. Therefore the value is bounded by

$$\sum_{i=1}^{n} \max(a_1, \ldots, a_i) \le \sum_{i=1}^{n} M = nM.$$

So $nM$ is the absolute best possible value.

Can we reach it? Yes. Pick any index $p$ where $a_p = M$. If $p = 1$, do nothing. Otherwise, swap $a_1$ and $a_p$.

After that, the array starts with $M$, so every prefix contains $M$. Since no element is bigger than $M$, every prefix maximum is exactly $M$:

$$\max(a_1, \ldots, a_i) = M \quad \text{for all } 1 \le i \le n.$$

Therefore the value becomes

$$M + M + \cdots + M = nM.$$

Since $nM$ is both an upper bound and achievable in at most one swap, it is the answer. No need for fancy swap simulation; that would be bringing a cannon to a spoon fight.

Edge cases:

• If the maximum is already first, skipping the swap is optimal.
• If there are multiple maximums, any one works.
• $n=2$ follows the same argument.

Complexity: $O(n)$ per test case, with $O(1)$ extra memory.