题目描述

Bessie 和 Farmer John 正在玩一个关于牛奶桶的游戏。

一排放着 \(N\) 个牛奶桶，满足 \(2 \le N \le 2 \cdot 10^5\)。从左到右第 \(i\) 个桶中初始有 \(a_i\) 加仑牛奶，满足 \(0 \le a_i \le 10^9\)。

游戏分两个阶段。

阶段 1

Farmer John 可以交换任意一对相邻的桶。每进行一次相邻交换，需要花费 \(1\) 枚硬币。他可以交换任意多次。

阶段 2

交换完成后，重复执行以下操作，直到只剩下一个桶：

• 任选一对相邻的桶，它们当前的牛奶量分别为 \(a_i\) 和 \(a_{i+1}\)
• 把这两个桶合并成一个新桶，牛奶量变为 \(\frac{a_i+a_{i+1}}{2}\)

你的任务是：为了让最后剩下的那个桶中的牛奶量尽可能大，求阶段 1 中至少要花多少枚硬币。

输入格式

第一行包含整数 \(T\)，表示测试组数，满足 \(1 \le T \le 100\)。

对于每组测试数据：

• 第一行一个整数 \(N\)
• 第二行 \(N\) 个整数 \(a_1,a_2,\dots,a_N\)

保证所有测试数据中 \(N\) 的总和不超过 \(5 \cdot 10^5\)。

输出格式

对于每组测试数据，输出一行一个整数，表示答案。

样例 1

输入

2
3
0 0 1
3
0 1 0

输出

0
1

说明

第一个测试中，不需要交换任何桶。第二阶段中先合并前两个桶，再合并剩下的两个桶，最终可以得到 \(0.5\)，并且这是最大可能值。

第二个测试中，如果不先交换，就无法得到 \(0.5\)。只需交换前两个桶一次即可达到最优。

样例 2

输入

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

说明

对于第一个测试，可以先把第二个和第三个桶交换，得到 [9,9,4,2]。然后按如下方式合并：

• [9,9,4,2]，合并后两个桶，得到 [9,9,3]
• [9,9,3]，合并后两个桶，得到 [9,6]
• [9,6]，合并这两个桶，得到 [7.5]

可以证明 \(7.5\) 已经是最终最大值，而为了达到这个最大值，最少需要 \(1\) 次交换。

数据范围

• 输入 3-4：\(a_i \le 1\) 且 \(N \le 2000\)（并且 \(N\) 总和不超过 \(5000\)）
• 输入 5-6：\(a_i \le 1\)
• 输入 7-9：\(N \le 2000\)（并且 \(N\) 总和不超过 \(5000\)）
• 输入 10-14：无额外限制

命题信息

原题命题：Charlie Yang