E. Мощность точек
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$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$$$, то есть сумму $$$f_p$$$ по всем целочисленным точкам от $$$1$$$ до $$$10^9$$$.

Например, если начальные координаты $$$[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$$$.

Входные данные

Первая строка содержит целое число $$$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$$$.

Выходные данные

Для каждого набора выведите $$$n$$$ чисел, $$$i$$$-е из которых равно сумме мощностей всех точек для $$$s=x_i$$$.

Пример
Входные данные
3
3
1 4 3
5
1 2 5 7 1
4
1 10 100 1000
Выходные данные
8 7 6
16 15 18 24 16
1111 1093 1093 2893
Примечание

В первом наборе входных данных мы сначала выбираем $$$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$$$.