Шоссе 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\).
Вам разрешено проделывать следующую операцию любое (в том числе ноль) количество раз: выбрать машину, стоящую в пробке, и переместить ее из ее текущего участка в любой другой участок.
Найдите минимальное неудобство, которого возможно достичь.
Выходные данные
Для каждого набора входных данных выведите строку, содержащую одно целое число — минимальное неудобство, которого возможно достичь, применяя указанную операцию любое (в том числе ноль) количество раз.
Примечание
В первом наборе входных данных вы можете переместить машину с \(3\)-го участка на \(1\)-й участок, чтобы получить неудобство, равное \(0\).
Во втором наборе перемещение любой машины не уменьшит неудобство гоночной трассы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
1 2 3
4
0 1 1 0
10
8 3 6 11 5 2 1 7 10 4
|
0
4
21
|