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 为了使最后一个桶中的牛奶量最大化而必须花费的最少硬币数量。
样例
输入样例 1
2
3
0 0 1
3
0 1 0输出样例 1
0
1说明 1
对于第一个测试用例，我们在第一阶段不需要交换任何牛奶桶。在第二阶段，Farmer John 可以合并前两个桶，然后合并仅剩的两个桶，从而得到最终的牛奶量为 0.5。可以证明这个最终量是最大的。
对于第二个测试用例，我们必须在第一阶段对前两个牛奶桶进行一次交换，以便在第二阶段达到 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输出样例 2
1
2
0
3说明 2
对于第一个测试用例，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：无额外限制。