AT_arc229_c.Sum of Average 2

You are given a length-$N$ sequence of positive integers $A=(A_1,A_2,\ldots,A_N)$.

Find the minimum possible value of $\displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor$ after rearranging $A$ in any order.

You are given $T$ test cases; solve each of them.

给你一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\ldots,A_N)$。

在对 $A$ 进行任意重排后，求 $\displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor$ 的最小可能值。

你将得到 $T$ 组测试数据；请分别求解每组数据。

The input is given from Standard Input in the following format:

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

Each test case is given in the following format:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

输入从标准输入中按以下格式给出：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每个测试用例按以下格式给出：

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

Output the answers for the test cases in order, separated by newlines.

按顺序输出测试用例的答案，答案之间用换行符分隔。

Sample 1 Explanation:
Consider the first test case.

For example, rearranging $A$ as $(3,2,1,4)$ gives $\displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor=\left\lfloor\frac52\right\rfloor+\left\lfloor\frac32\right\rfloor+\left\lfloor\frac52\right\rfloor=5$.

No matter how $A$ is rearranged, the value of $\displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor$ is at least $5$, so the answer is $5$.

Constraints

• $1\le T\le 10^5$
• $2\le N\le 2\times 10^5$
• $1\le A_i\le 10^9$
• The sum of $N$ over all test cases is at most $2\times 10^5$.
• All input values are integers.

样例 1 解释：
考虑第一个测试用例。

例如，将 $A$ 重排为 $(3,2,1,4)$，可得

$$\displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor=\left\lfloor\frac52\right\rfloor+\left\lfloor\frac32\right\rfloor+\left\lfloor\frac52\right\rfloor=5。$$

无论 $A$ 如何重排，$\displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor$ 的值均不小于 $5$，因此答案为 $5$。

约束条件

• $1\le T\le 10^5$
• $2\le N\le 2\times 10^5$
• $1\le A_i\le 10^9$
• 所有测试用例的 $N$ 之和不超过 $2\times 10^5$。
• 所有输入值均为整数。