CF2165A.Cyclic Merging

You are given $n$ non-negative integers $a_1,a_2,\ldots,a_n$ arranged on a ring. For each $1\le i \lt n$, $a_i$ and $a_{i+1}$ are adjacent; $a_1$ and $a_n$ are adjacent.

You need to perform the following operation exactly $n-1$ times:

• Choose any pair of adjacent elements on the ring, let their values be $x$ and $y$, and merge them into a single element of value $\max(x,y)$ with cost $\max(x,y)$.

Note that this operation will decrease the size of the ring by $1$ and update the adjacent relationships accordingly.

Please calculate the minimum total cost to merge the ring into one element.

给你 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$，它们按环形排列。对于每个 $1\le i \lt n$，$a_i$ 与 $a_{i+1}$ 相邻；$a_1$ 与 $a_n$ 相邻。

你需要恰好执行以下操作 $n-1$ 次：

• 在环上任选一对相邻元素，设其值分别为 $x$ 和 $y$，将它们合并为一个值为 $\max(x,y)$ 的新元素，此次合并的代价为 $\max(x,y)$。

注意：该操作会使环的大小减少 $1$，并相应地更新相邻关系。

请计算将整个环合并为单个元素所需的最小总代价。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($2\le n\le 2\cdot 10^5$).

The following line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0\le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2\le n\le 2\cdot 10^5$）。

接下来的一行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0\le a_i \le 10^9$）。

保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。

For each test case, please print a single integer — the minimum total cost.

对于每个测试用例，请输出一个整数——最小总成本。

In the first test case, we can achieve a cost of $6$ on $[1,1,3,2]$ as follows:

• Merge indexes $1$ and $2$ with a cost of $1$, the ring becomes $[1,3,2]$.
• Merge indexes $1$ and $3$ with a cost of $2$, the ring becomes $[3,2]$.
• Merge indexes $1$ and $2$ with a cost of $3$, the ring becomes $[3]$.

The total cost is $1+2+3=6$. It can be proven that it is impossible to achieve a lower cost; thus, the answer is indeed $6$.

In the second test case, the only option is to merge the two elements, with a cost of $2$.

在第一个测试用例中，我们可以在序列 $[1,1,3,2]$ 上实现总代价为 $6$，具体步骤如下：

• 合并下标 $1$ 和 $2$，代价为 $1$，环变为 $[1,3,2]$；
• 合并下标 $1$ 和 $3$，代价为 $2$，环变为 $[3,2]$；
• 合并下标 $1$ 和 $2$，代价为 $3$，环变为 $[3]$。

总代价为 $1+2+3=6$。可以证明无法获得更低的代价；因此答案确为 $6$。

在第二个测试用例中，唯一的选择是合并两个元素，代价为 $2$。