给你 $$$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$$$。
输出
对于每个测试用例,请打印一个整数 - 最低总成本。
示例
输入复制
341 1 3 220 271 1 4 5 1 4 1
输出复制
6219
注意
在第一个测试用例中,我们可以在 $$$[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$$$。