对和
题号：NC313181
时间限制：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。他定义数组的“和谐值”为：

\displaystyle H(a) = \sum_{i=1}^{n} \sum_{j=i+1}^{n} \left\lfloor \frac{a_i + a_j}{2} \right\rfloor

\hspace{15pt}你的任务是求出“和谐值” H(a)。

【名词解释】
\hspace{15pt}\lfloor x \rfloor：代表对 x 进行下取整操作，得到不超过 x 的最大整数。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1 \leqq T \leqq 10^5\right) 代表数据组数，每组测试数据描述如下：
\hspace{23pt}\bullet\,第一行输入一个整数 n\left(1 \leqq n \leqq 2 \times 10^5\right)，表示数组的长度。
\hspace{23pt}\bullet\,第二行输入 n 个整数 a_1, a_2, \dots, a_n\left(1 \leqq a_i \leqq 10^6\right)，表示数组的元素。
\hspace{15pt}除此之外，保证单个测试文件的 n 之和不超过 2 \times 10^5。

输出描述:

\hspace{15pt}对于每一组测试数据，新起一行输出一个整数，表示该数组的“和谐值”。
示例1

输入

复制 
3
3
1 2 3
4
5 5 5 5
2
100000 1

输出

复制 
5
30
50000

说明

\hspace{15pt}对于第一组测试数据，H(a)=\left\lfloor\tfrac{1+2}{2}\right\rfloor+\left\lfloor\tfrac{1+3}{2}\right\rfloor+\left\lfloor\tfrac{2+3}{2}\right\rfloor=1+2+2=5。