Шоссе 201 — самая оживлённая улица в Рокпорт-Сити. Машины, стоящие в пробках, создают помехи для гонок, особенно когда их много. Гоночная трасса, проходящая через это шоссе, разделена на $$$n$$$ участков. Вам дан массив $$$a$$$, в котором $$$a_i$$$ равно количеству машин, стоящих в пробках на $$$i$$$-м участке. Положим неудобством гоночной трассы значение $$$\sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} \lvert a_i-a_j\rvert$$$, где $$$|x|$$$ — модуль числа $$$x$$$.
Вам разрешено проделывать следующую операцию любое (в том числе ноль) количество раз: выбрать машину, стоящую в пробке, и переместить ее из ее текущего участка в любой другой участок.
Найдите минимальное неудобство, которого возможно достичь.
Первая строка содержит одно целое число $$$t$$$ ($$$1\leq t\leq 10\,000$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$).
Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i\leq 10^9$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите строку, содержащую одно целое число — минимальное неудобство, которого возможно достичь, применяя указанную операцию любое (в том числе ноль) количество раз.
3 3 1 2 3 4 0 1 1 0 10 8 3 6 11 5 2 1 7 10 4
0 4 21
В первом наборе входных данных вы можете переместить машину с $$$3$$$-го участка на $$$1$$$-й участок, чтобы получить неудобство, равное $$$0$$$.
Во втором наборе перемещение любой машины не уменьшит неудобство гоночной трассы.
| Codeforces Round 730 (Div. 2) |
|---|
| Закончено |
