AT_arc229_c [ARC229C] Sum of Average 2

给定一个长度为 $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$ 组测试用例，请你依次解决每组测试数据。

输入由标准输入给出，格式如下： > $T$ > $\text{case}_1$ > $\text{case}_2$ > $\vdots$ > $\text{case}_T$ 每组测试数据的格式为： > $N\ A_1\ A_2\ \ldots\ A_N$

按测试用例顺序输出答案，每个答案一行。

### 样例解释 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\frac{5}{2}\right\rfloor + \left\lfloor\frac{3}{2}\right\rfloor + \left\lfloor\frac{5}{2}\right\rfloor = 5。 $$ 无论如何重新排列 $A$，$\displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}{2}\right\rfloor$ 的值至少为 $5$，因此答案为 $5$。 ### 数据范围 - $1 \leq T \leq 10^5$ - $2 \leq N \leq 2\times 10^5$ - $1 \leq A_i \leq 10^9$ - 所有测试用例的 $N$ 之和不超过 $2\times 10^5$ - 所有输入数值均为整数。 由 ChatGPT 5 翻译