题目描述

活动结束后，算法协会需要打包剩余的物资。

目前有 $n$ 个包裹从左到右排成一行，第 $i$ 个包裹的重量为 $a_{i}$。工作人员会不断合并包裹，直到只剩下一个包裹。

每次操作严格按照以下规则进行：

1. 在当前相邻的两个包裹中，选择重量之和最小的一对。

2. 如果有多对包裹满足条件，选择其中最靠左的一对。

3. 将它们合并为一个新包裹，其重量等于原来两个包裹的重量之和。新包裹放在它们原来的位置，其他包裹的相对顺序不变。

4. 本次操作消耗的时间，等于新包裹的重量。

请计算严格按照上述规则完成所有合并操作所消耗的总时间。如果最初只有一个包裹，则无需进行操作，总时间为 $0$。

输入格式

第一行包含一个整数 $t$（$1\le t\le10^{4}$），表示测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $n$（$1\le n\le2\times10^{5}$），表示包裹的数量。

• 第二行包含 $n$ 个整数 $a_{1},a_{2},\ldots,a_{n}$（$1\le a_{i}\le10^{5}$），依次表示从左到右各个包裹的重量。

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

输出格式

对于每个测试用例，输出一行一个整数，表示完成所有合并操作所消耗的总时间。

4
5
4 1 3 2 5
3
1 100 1
4
1 2 1 2
1
7

35
203
12
0

样例解释

第一组测试用例中，包裹的重量序列依次变化为：

$$[4,1,3,2,5]\rightarrow[4,4,2,5]\rightarrow[4,6,5]\rightarrow[10,5]\rightarrow[15].$$

四次操作分别消耗 $4,6,10,15$ 的时间，总时间为 $35$。

第二组测试用例中，两个重量为 $1$ 的包裹并不相邻。第一次合并最左边的两个包裹，消耗 $101$ 的时间；第二次合并剩余的两个包裹，消耗 $102$ 的时间。总时间为 $203$。

第三组测试用例中，最初三对相邻包裹的重量之和均为 $3$，因此第一次必须合并最左边的一对。重量序列依次为 $[1,2,1,2]$、$[3,1,2]$、$[3,3]$、$[6]$，总时间为 $3+3+6=12$。

第四组测试用例中无需合并，总时间为 $0$。