题目描述

给定 $n$ 个非负整数 $a_1,a_2,\dots,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$）。

• 对于每个测试用例：

  • 第一行包含一个整数 $n$，表示环上元素的个数（$2\le n\le 2\cdot10^5$）。
  • 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示环上元素的值（$0\le a_i\le 10^9$）。

数据保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^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]$ 的一种最优合并过程是：

  1. 合并下标 $1$ 与 $2$（值分别为 $1,1$），代价 $1$，得到 $[1,3,2]$；
  2. 合并当前位置上的相邻元素（对应值 $1,2$），代价 $2$，得到 $[3,2]$；
  3. 合并剩下的两个元素，代价 $3$，得到 $[3]$。总代价 $1+2+3=6$，无法更低。

• 第二个样例：只有两个元素，唯一一次合并代价为 $\max(0,2)=2$。