点击此处下载附加样例文件

题目描述

N 个气球排成一排，从左到右依次编号为 1, 2, 3, ……, N。

每个气球有一个直径，编号为 i 的气球的直径是 Di。

如果两个气球 x 和 y 相邻，那么你可以施展魔法，这两个气球会向中间靠拢合并成一个气球，直径变成 (Dx+Dy)/2。

你可以不断地施展魔法，直到所有气球最终变成一个气球。

你希望最后得到一个尽可能大的气球。

为此，在施展魔法之前，你可以把两个相邻的气球交换位置。你可以交换任意次，每次交换你可以选择任意两个相邻的气球。但是每次交换，你需要付出 1 的代价。而且在你一旦开始施展魔法之后，你将不能再交换气球的位置。

问：为了使得最后得到的气球最大，你最少需要付出多少代价？

多组数据。

输入格式

第一行：一个整数 T，表示数据组数。

对于每组数据：

• 第一行：一个整数 N
• 第二行：N 个整数 Di

输出格式

共 T 行，每组数据的答案占一行。

输入样例1

3
3
1 0 0
3
0 1 0
6
0 0 2 0 0 0

输出样例1

0
1
2

数据范围

共 14 个测试点：$1 ≤ T ≤ 100$, $2 ≤ N ≤ 2×10^5$（$0 ≤ D_i ≤ 10^9$），每个测试点的所有 $N$ 之和不超过 $5×10^5$。

其中有 5 个测试点：$D_i ≤ 1$。其中又有 3 个测试点：$N ≤ 2000$（ $N$ 之和 $≤ 5000$）

另有 3 个测试点：$N ≤ 2000$（ $N$ 之和 $≤ 5000$）