小苯的线性dp

题号：NC288923
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯有一个由 $n$ 个正整数组成的数组 $\{a_1, a_2, \dots, a_n\}$ 。他打算执行一些“合并”操作来最大化数组的极差。一次“合并”操作描述为：
$\hspace{23pt}\bullet\,$ 选择一对相邻的数字，将这两个数字合并为它们相加的和。形式化的，选择一个下标 $i\left(1 \leqq i<n\right)$ ，执行 $a_i:=a_i+a_{i+1}$ ，随后删除 $a_{i+1}$ ，其余元素按照原有顺序前后拼接。

$\hspace{15pt}$ 而小红觉得，如果允许小苯进行任意次“合并”操作的话有些太简单了，因此她限定小苯必须恰好执行“合并”操作 $k$ 次，求最终数组能得到的最大极差。
$\hspace{15pt}$ 现在，请你独立地对 $k\left(0 \leqq k < n\right)$ 的每一个 $k$ ，都求出上述问题的答案吧。

$\hspace{15pt}$ 数组的极差定义为数组中最大值和最小值的差。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入一个正整数  代表数组中的元素个数。 
第二行输入  个正整数  代表数组中的元素。 

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行。输出  个整数 ，其中  表示恰好执行  次“合并”操作后，数组的最大极差。

示例1

输入

复制

输出

复制

3 6 6 0
3 6 6 6 0

说明

对于第一组测试数据，以  为例：
合并  和 ，数组变为 ；
合并  和 ，数组变为 。
此时，数组的极差为 ，我们可以证明，这是全部合并方案中最大的。