CFCF2165A.Cyclic Merging

给定 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$，这些数排成一个环。对于每个 $1\le i< n$，$a_i$ 与 $a_{i+1}$ 相邻；$a_1$ 与 $a_n$ 也相邻。

你需要恰好进行 $n-1$ 次如下操作：

• 每次选择环上任意一对相邻的元素，记它们的值分别为 $x$ 和 $y$，将它们合并为一个值为 $\max(x,y)$ 的元素，花费为 $\max(x,y)$。

注意，每次操作会使环的长度减少 $1$，相邻关系也会随之更新。

请计算将环合并为一个元素的最小总花费。

每组测试数据包含多组测试用例。第一行为测试用例数 $t$，满足 $1 \le t \le 10^4$。接下来是 $t$ 组测试用例。

每组测试用例的第一行包含一个整数 $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$。

对于每组测试用例，输出一个整数，表示将环合并为一个元素所需的最小总花费。

在第一个测试用例中，我们可以对 $[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$。