小苯的平衡序列

题号：NC297926
时间限制：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$ 。他定义序列的"平衡度"为：
$\sum_{i=1}^{n} |a_i - \text{median}|$

$\hspace{15pt}$ 其中 $\rm median$ 表示序列的中位数。如果序列长度是偶数，则中位数定义为较小的那个中间数（即下中位数）。

$\hspace{15pt}$ 现在允许从序列中删除恰好一个元素，请计算删除哪个元素可以使剩下的序列的平衡度最小，并输出这个最小的平衡度。

输入描述:

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

第一行一个整数 ，表示序列长度。
第二行  个整数 ，表示给定的序列。

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

输出描述:

对于每组测试数据：
在单独的一行输出一个整数表示删除一个元素后能得到的最小平衡度。

示例1

输入

复制

2
5
1 2 3 4 5
6
4 1 5 3 2 6

输出

复制

4
6

说明

第一组数据：
- 删除  后，新中位数为  ，平衡度为 。
第二组数据：
- 删除  后，新中位数为 ，平衡度为