P1008：铁棒切割

题目描述

有 $n$ 根铁棒，其中第 $i$ 根铁棒的长度为 $a_i$。这 $n$ 根铁棒按照 $1,2,3,\dots,n$ 的顺序焊接在一起，形成一根非常长的铁棒以供使用。焊接两个相邻的铁棒会产生一个焊点，总共会有 $n - 1$ 个焊点。

小 Q 需要将这根长铁棒切割回 $n$ 根铁棒。每次他可以选择一根至少有一个焊点的铁棒，并选择一个焊点将铁棒从焊点处切割成两根铁棒，然后记得到的两根铁棒的长度分别为 $l_1$ 和 $l_2$。这次切割的不平衡度定义为 $|l_1 - l_2|$，而切割的代价定义为 $\min\{l_1, l_2\} \times \lceil\log_2(l_1 + l_2)\rceil$。请注意，$|x|$ 表示 $x$ 的绝对值，$\lceil\log_2(y)\rceil$ 表示满足 $2^z \ge y$ 的最小整数 $z$。

小 Q 希望这 $n - 1$ 次切割的不平衡度 $b_1, b_2, \dots, b_{n-1}$ 满足 $b_1 \ge b_2 \ge \dots \ge b_{n-1}$，并且这 $n - 1$ 次切割的总代价最小。你需要对每个 $i = 1,2,\dots,n - 1$ 计算第一次切割在第 $i$ 根铁棒和第 $i + 1$ 根铁棒之间的焊点时最小的总代价，或者指出不可能切割出 $n$ 根铁棒。

输入输出格式

输入

输入的第一行包含一个整数 $T\ (1 \le T \le 200)$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n\ (2 \le n \le 420)$，表示铁棒的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n\ (1 \le a_i \le 10^9)$，表示铁棒的长度。

保证所有测试数据 $n$ 的总和不超过 $420$。

输出

对于每组测试数据，输出一行包含 $n - 1$ 个整数，其中第 $i$ 个整数表示第一次切割在第 $i$ 根铁棒和第 $i + 1$ 根铁棒之间的焊点时最小的总代价，或者输出 $-1$ 表示不可能切割出 $n$ 根铁棒。

样例

3
3
8 9 7
3
1 5 9
3
3 1 4

68 75
24 -1
-1 -1

数据范围

• $1 \le T \le 200$
• $2 \le n \le 420$
• $1 \le a_i \le 10^9$
• $\sum n \le 420$