Есть \(n\) коробок конфет, \(i\)-я коробка содержит \(a_i\) конфет.
У вас также есть \(n\) друзей, каждому из которых вы решили подарить коробку конфет. Вы не хотите, чтобы кто-то из друзей расстраивался, поэтому решили съесть несколько (возможно, ноль) конфет из каждой коробки так, чтобы во всех коробках было одинаковое количество конфет. Обратите внимание, что вы можете съесть разное количество конфет из разных коробок, и вы не можете добавлять конфеты ни в одну из коробок.
Какое минимальное количество конфет нужно съесть, чтобы выполнить требования?
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальное количество конфет, которые вам нужно съесть, чтобы выполнить требования.
Примечание
В первом наборе вы можете съесть \(1\) конфету из второй коробки, \(2\) конфеты из третьей коробки, \(3\) конфеты из четвертой коробки и \(4\) конфеты из пятой коробки. Теперь распределение конфет по коробкам выглядит так: \([1, 1, 1, 1, 1]\). Вы съели всего \(0 + 1 + 2 + 3 + 4 = 10\) конфет, поэтому ответ равен \(10\).
Лучший ответ для второго набора получается, если уменьшить количество конфет во всех коробках до \(5\). Так, вы съедите \(995 + 995 + 0 + 995 + 995 + 995 = 4975\) конфет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5
1 2 3 4 5
6
1000 1000 5 1000 1000 1000
10
1 2 3 5 1 2 7 9 13 5
3
8 8 8
1
10000000
|
10
4975
38
0
0
|