| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 61 | 40 | 28 | 57.143% |
Однажды, вернувшись в свою башню, Мерлин обнаружил, что Моргана наложила проклятие на все его сосуды с эликсиром мудрости.
Мерлин знает, как снять проклятие, но соответствующее заклинание требует, чтобы во всех сосудах, к которым оно применяется, было равное количество эликсира.
Чтобы добиться этого, Мерлин решил действовать следующим образом. Он выбирает несколько сосудов и переливает весь элексир из выбранных сосудов в оставшиеся. Он может распределить переливаемый элексир между оставшимися сосудами произвольным образом. После того, как весь элексир из выбранных сосудов перелит, Мерлин разбивает опустошенные сосуды (с них проклятие уже не снять), выбрасывает осколки и применяет заклинание снятия проклятия к оставшимся сосудам.
Помогите волшебнику узнать, какое наименьшее количество сосудов ему придется разбить, чтобы снять проклятие Морганы.
В первой строке входного файла находится число $n$ (2ドル \le n \le 10^5$) --- количество сосудов. Во второй строке содержатся $n$ чисел $a_1, a_2, \ldots, a_n$ (1ドル \le a_i \le 10^9$) --- количество литров эликсира мудрости в каждом сосуде.
Выведите в выходной файл минимальное количество сосудов, которые Мерлину придется разбить.
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 литр из пятого в четвертый, после чего разбить первый и пятый сосуды.