题目描述

Bessie 向 Farmer John 发起了一个涉及牛奶桶的游戏挑战！有 $N$ 个（$2 \leq N \leq 2 \cdot 10^5$）牛奶桶排成一行。从左数第 $i$ 个桶最初装有 $a_i$（$0 \leq a_i \leq 10^9$）加仑牛奶。

游戏分为两个阶段：

阶段 1：Farmer John 可以交换任意两个相邻的桶。他可以执行任意多次交换，但每次交换需要花费 1 枚硬币。

阶段 2：交换完成后，Farmer John 执行以下操作，直到只剩下一个桶为止：选择两个相邻的桶，其牛奶量分别为 $a_i$ 和 $a_{i+1}$，并将这两个桶替换为一个桶，新桶中装有 $\frac{a_i+a_{i+1}}2$ 加仑牛奶，放在它们原来的位置。

你的目标是确定在交换阶段中，Farmer John 必须花费的最小硬币数量，以便在所有合并完成后，最终桶中的牛奶量最大化。

输入格式

第一行包含一个整数 $T$（$1 \leq T \leq 100$）：独立测试用例的数量。

接下来，对于每个测试用例，第一行包含一个整数 $N$：牛奶桶的数量。第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$，用空格分隔：每个桶中牛奶的加仑数。

保证所有测试用例的 $N$ 之和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，输出 Farmer John 为了最大化最终桶中的牛奶量而必须花费的最小硬币数量。

2
3
0 0 1
3
0 1 0

0
1

4
4
9 4 9 2
6
0 0 2 0 0 0
3
2 0 1
9
3 3 3 10 3 2 13 14 13

1
2
0
3

提示

对于第一个测试用例，我们在第一阶段不需要交换任何牛奶桶。在第二阶段，Farmer John 可以合并前两个桶，然后合并剩下的两个桶，最终得到 $0.5$ 加仑的牛奶。可以证明，这个最终量是最大的。

对于第二个测试用例，我们必须在第一阶段交换前两个牛奶桶一次，才能在第二阶段得到 $0.5$ 加仑的最终量。可以证明，如果不在第一阶段进行交换，我们无法达到 $0.5$ 加仑的最终量。

---

对于第一个测试用例，Farmer John 可以在第一阶段交换第二个和第三个桶。然后，在第二阶段，Farmer John 可以执行以下操作：

• $[9,9,4,2]$ -> 合并第三和第四个桶 ->
• $[9,9,3]$ -> 合并第二和第三个桶 ->
• $[9,6]$ -> 合并第一和第二个桶 ->
• $[7.5]$

最终的牛奶量为 $7.5$，这是可能的最大值。可以证明，即使进行更多的交换，最终量也无法超过 $7.5$，而如果交换次数更少，最终量也无法达到 $7.5$。

---

• 输入 $3$-$4$：$a_i\le 1$ 且 $N\le 2000$（$N$ 之和 $\le 5000$）
• 输入 $5$-$6$：$a_i\le 1$
• 输入 $7$-$9$：$N\le 2000$（$N$ 之和 $\le 5000$）
• 输入 $10$-$14$：无额外约束。

翻译由 DeepSeek V3 完成