← 返回题目列表

Codeforces · 2165/A

A. 循环合并

中文机器翻译题面 查看原题

给你 $$$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$$$ 并相应地更新相邻关系。

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

输入

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

输出

对于每个测试用例,请打印一个整数 - 最低总成本。

示例

输入
复制

3
4
1 1 3 2
2
0 2
7
1 1 4 5 1 4 1

输出
复制

6
2
19

注意

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