Подарки

Мальчику Васе подарили на 23 февраля n коробок с конфетами, в i-й из них лежало ai конфет. На самом деле, Вася не очень любит конфеты, поэтому он решил подарить их девочкам на 8 марта. Чтобы не обижать ни одну из девочек, Вася хочет подарить каждой из них поровну конфет. При этом Вася решил, что имея n подарочных коробок, глупо отказываться от возможности использования даже одной из них, поэтому он составит ровно n подарков из имеющихся у него конфет, переложив их между коробками некоторым образом. При этом, возможно, ему придется съесть несколько конфет самому, иначе будет невозможно составить n одинаковых подарков. Помогите Васе определить минимальное количество конфет, которое ему придётся съесть.
Входные данные
В первой строке задано натуральное число n (1 ≤ n ≤ 105) — количество подарков, которые есть у Васи.
Во второй строке заданы n чисел a1, a2, ..., an (1 ≤ ai ≤ 104), разделенные пробелом и задающие количество конфет в каждой из коробок.
Выходные данные
В единственной строке выведите целое неотрицательное число k — минимальное число конфет, которое придётся съесть Васе, чтобы составить n одинаковых подарков из оставшихся конфет.
Sample Input 1:
6
1 2 3 4 5 6
Sample Output 1:
3
Sample Input 2:
3
3 6 12
Sample Output 2:
0

0