CF1857E.Power of Points

You are given $n$ points with integer coordinates $x_1,\dots x_n$, which lie on a number line.

For some integer $s$, we construct segments [$s,x_1$], [$s,x_2$], $\dots$, [$s,x_n$]. Note that if $x_i \lt s$, then the segment will look like [$x_i,s$]. The segment [$a, b$] covers all integer points $a, a+1, a+2, \dots, b$.

We define the power of a point $p$ as the number of segments that intersect the point with coordinate $p$, denoted as $f_p$.

Your task is to compute $\sum\limits_{p=1}^{10^9}f_p$ for each $s \in {x_1,\dots,x_n}$, i.e., the sum of $f_p$ for all integer points from $1$ to $10^9$.

For example, if the initial coordinates are $[1,2,5,7,1]$ and we choose $s=5$, then the segments will be: $[1,5]$,$[2,5]$,$[5,5]$,$[5,7]$,$[1,5]$. And the powers of the points will be: $f_1=2, f_2=3, f_3=3, f_4=3, f_5=5, f_6=1, f_7=1, f_8=0, \dots, f_{10^9}=0$. Their sum is $2+3+3+3+5+1+1=18$.

给你 $n$ 个具有整数坐标的点 $x_1,\dots,x_n$，它们位于一条数轴上。

对某个整数 $s$，我们构造线段 $[s,x_1]$, $[s,x_2]$, $\dots$, $[s,x_n]$。注意：若 $x_i < s$，则该线段写作 $[x_i,s]$。线段 $[a, b]$ 覆盖所有整数点 $a, a+1, a+2, \dots, b$。

我们定义点 $p$ 的权值为覆盖坐标 $p$ 的线段数量，记作 $f_p$。

你的任务是：对每个 $s \in \{x_1,\dots,x_n\}$，计算 $\sum\limits_{p=1}^{10^9}f_p$，即对从 $1$ 到 $10^9$ 的所有整数点 $p$，求其权值 $f_p$ 的总和。

例如，若初始坐标为 $[1,2,5,7,1]$，且选择 $s=5$，则所构造的线段为：$[1,5]$, $[2,5]$, $[5,5]$, $[5,7]$, $[1,5]$。各点的权值为：$f_1=2$, $f_2=3$, $f_3=3$, $f_4=3$, $f_5=5$, $f_6=1$, $f_7=1$, $f_8=0$, $\dots$, $f_{10^9}=0$。其总和为 $2+3+3+3+5+1+1=18$。

The first line contains an integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The first line of each test case contains an integer $n$ ($1 \le n \le 2\cdot 10^5$) — the number of points.

The second line contains $n$ integers $x_1,x_2 \dots x_n$ ($1 \le x_i \le 10^9$) — the coordinates of the points.

It is guaranteed that the sum of the values of $n$ over all test cases does not exceed $2\cdot 10^5$.

第一行包含一个整数 $t$（$1\le t\le 10^4$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2\cdot 10^5$）——点的数量。

每个测试用例的第二行包含 $n$ 个整数 $x_1,x_2 \dots x_n$（$1 \le x_i \le 10^9$）——各点的坐标。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

For each test case, output $n$ integers, where the $i$-th integer is equal to the sum of the powers of all points for $s=x_i$.

对于每个测试用例，输出 $n$ 个整数，其中第 $i$ 个整数等于当 $s=x_i$ 时所有点的幂之和。

In the first test case we first choose $s=x_1=1$, then the following segments are formed: $[1,1]$,$[1,4]$,$[1,3]$.

The powers of the points will be as follows: $f_1=3, f_2=2, f_3=2, f_4=1, f_5=0 \dots$ The sum of powers of the points: $3+2+2+1+0+\dots+0=8$.

After that we choose $s=x_2=4$. Then there will be such segments: $[1,4]$,$[4,4]$,$[3,4]$, and powers of the points are $f_1=1, f_2=1, f_3=2, f_4=3$.

At the end we take $s=x_3=3$ and the segments look like this: $[1,3]$,$[3,4]$,$[3,3]$, the powers of the points are $f_1=1, f_2=1, f_3=3, f_4=1$.

在第一个测试用例中，我们首先选择 $s=x_1=1$，随后形成的区间为：$[1,1]$、$[1,4]$、$[1,3]$。

各点的权值如下：$f_1=3,\ f_2=2,\ f_3=2,\ f_4=1,\ f_5=0\ \dots$。所有点的权值之和为：$3+2+2+1+0+\dots+0=8$。

接着我们选择 $s=x_2=4$，此时形成的区间为：$[1,4]$、$[4,4]$、$[3,4]$，各点的权值为 $f_1=1,\ f_2=1,\ f_3=2,\ f_4=3$。

最后我们取 $s=x_3=3$，此时区间为：$[1,3]$、$[3,4]$、$[3,3]$，各点的权值为 $f_1=1,\ f_2=1,\ f_3=3,\ f_4=1$。