Cyclic Merging

Let’s name the important thing: gaps, not elements.

For each cyclic gap between neighboring elements, define

$$w_i = \max(a_i, a_{i+1}),$$

where $a_{n+1}=a_1$.

The answer is:

$$\sum_{i=1}^{n} w_i - \max_{i=1}^{n} w_i.$$

That’s the whole trick. Now let’s justify it properly, because otherwise this formula looks like it fell out of the sky wearing sunglasses.

Warm-up: merging a line

Suppose the numbers are not on a ring, but on a line:

$$b_1,b_2,\dots,b_m.$$

Define each line gap weight as

$$v_i = \max(b_i,b_{i+1}) \quad (1 \le i < m).$$

Claim: the minimum cost to merge this line into one element is

$$\sum_{i=1}^{m-1} v_i.$$

Why is this a lower bound?

Consider one original gap between $b_i$ and $b_{i+1}$. At some point, the block containing $b_i$ and the block containing $b_{i+1}$ must be merged together for the first time. That merge removes this original gap.

The merged block contains both $b_i$ and $b_{i+1}$, so its value, and therefore the merge cost, is at least

$$\max(b_i,b_{i+1}) = v_i.$$

There are exactly $m-1$ original gaps and exactly $m-1$ merges, so every gap contributes at least its weight. Therefore every strategy costs at least

$$\sum v_i.$$

Now the more important part: this lower bound is actually achievable.

Take any segment of the line. Let $M$ be the maximum value inside that segment. If the segment has length at least $2$, there is always some internal gap adjacent to an occurrence of $M$, and that gap has weight $M$.

Make that gap the last merge inside this segment. Then recursively merge the left part and the right part first.

By induction:

• the left part costs exactly the sum of its internal gap weights,
• the right part costs exactly the sum of its internal gap weights,
• the final merge costs exactly $M$, which equals the chosen gap weight.

So the whole segment costs exactly the sum of all its gap weights.

Therefore, for a line, the optimal cost is exactly the sum of adjacent maximums.

Back to the ring

A ring with $n$ elements has $n$ cyclic gaps:

$$(a_1,a_2), (a_2,a_3), \dots, (a_{n-1},a_n), (a_n,a_1).$$

Each merge removes one current boundary, which corresponds to one original cyclic gap. Since we do exactly $n-1$ merges, exactly $n-1$ of the $n$ original gaps get used. One original gap is left unused.

If gap $i$ is used, the merge removing it costs at least

$$w_i = \max(a_i,a_{i+1}).$$

So if the unused gap is $j$, the total cost is at least

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

To minimize this lower bound, we obviously want the unused gap to be the most expensive one. So every strategy costs at least

$$\sum_{i=1}^{n} w_i - \max_{i=1}^{n} w_i.$$

Can we achieve it? Yep.

Pick a cyclic gap with maximum weight and pretend to cut the ring there. Now the remaining elements form a line, and the line gaps are exactly all cyclic gaps except the one we cut.

From the line result, we can merge this line with cost equal to the sum of those remaining gap weights. Since all those line merges are valid ring merges too, this gives total cost

$$\sum_{i=1}^{n} w_i - \max_{i=1}^{n} w_i.$$

Lower bound matches construction, so we’re done. No weird priority queue, no fake Huffman cosplay, just gap accounting.

Algorithm

For each test case:

1. Compute $w_i=\max(a_i,a_{(i+1)\bmod n})$ for all $i$.
2. Add all $w_i$ into sum.
3. Track the largest $w_i$ as best.
4. Print sum - best.

The values can be up to $10^9$ and there are up to $2\cdot 10^5$ elements, so the answer can be around $2\cdot 10^{14}$. Use long long.

Complexity per test case: $O(n)$ time and $O(n)$ memory, or $O(1)$ extra memory if you want to stream carefully. The simple vector version is already totally fine.