每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数,每组测试数据描述如下:第一行输入一个正整数 代表数组中的元素个数。 第二行输入 个正整数 代表数组中的元素。 除此之外,保证单个测试文件的 之和不超过 。
对于每一组测试数据,新起一行。输出 个整数 ,其中 表示恰好执行 次“合并”操作后,数组的最大极差。
2 4 2 1 3 4 5 4 2 1 3 4
3 6 6 0 3 6 6 6 0
对于第一组测试数据,以 为例:合并 和 ,数组变为 ;合并 和 ,数组变为 。此时,数组的极差为 ,我们可以证明,这是全部合并方案中最大的。