Задача: Мерлин
Однажды, вернувшись в свою башню, Мерлин обнаружил, что Моргана наложила проклятие на
все его сосуды с эликсиром мудрости.
Мерлин знает, как снять проклятие, но соответствующее заклинание требует, чтобы во всех
сосудах, к которым оно применяется, было равное количество эликсира.
Чтобы добиться этого, Мерлин решил действовать следующим образом. Он выбирает несколько
сосудов и переливает весь эликсир из выбранных сосудов в оставшиеся. Он может распределить
переливаемый эликсир между оставшимися сосудами произвольным образом. После того, как весь
эликсир из выбранных сосудов перелит, Мерлин разбивает опустошенные сосуды (с них проклятие
уже не снять), выбрасывает осколки и применяет заклинание снятия проклятия к оставшимся
сосудам.
Помогите волшебнику узнать, какое наименьшее количество сосудов ему придется разбить,
чтобы снять проклятие Морганы.
Формат входных данных
В первой строке входного файла находится число n (2 ≤ n ≤ 105) — количество сосудов. Во
второй строке содержатся n чисел a1, a2, . . . , an (1 ≤ ai ≤ 109) — количество литров эликсира
мудрости в каждом сосуде.
Формат выходных данных
Выведите в выходной файл минимальное количество сосудов, которые Мерлину придется
разбить.
Пример
Ввод
3
2 3 2
Вывод
1
Ввод:
4
4 4 4 4
Вывод
0
Ввод
5
1 2 3 4 5
Вывод
2
В первом примере можно, например, перелить 0.5 литра эликсира из первого сосуда во второй
и 1.5 литра в третий, после чего разбить первый сосуд.
Во втором сосуды исходно содержат равное количество эликсира, можно ничего не переливать.
В третьем примере можно, например, перелить 1 литр эликсира из первого сосуда во второй, по
2 литра из пятого во второй и третий, 1 литр из пятого в четвертый, после чего разбить первый и
пятый сосуды.
Ваш ответ: