У Поликарпа есть \(n\) друзей, у \(i\)-го из которых есть \(a_i\) конфет. Друзьям Поликарпа не нравится, когда у них различается количество конфет. Иными словами, они хотят, чтобы все \(a_i\) были равны. Чтобы добиться этого, Поликарп делает следующее ровно один раз:
- Поликарп выбирает \(k\) (\(0 \le k \le n\)) произвольных друзей (пусть он выбрал друзей с номерами \(i_1, i_2, \ldots, i_k\));
- Поликарп перераспределяет их конфеты среди всех \(n\) друзей, всего таких конфет \(a_{i_1} + a_{i_2} + \ldots + a_{i_k}\). При перераспределении для каждой конфеты из \(a_{i_1} + a_{i_2} + \ldots + a_{i_k}\) он выбирает нового владельца (любого из \(n\) друзей, конфета может вновь достаться старому владельцу).
Заметьте, что число \(k\) заранее не фиксировано и может быть произвольным. Ваша задача — найти минимальное возможное значение \(k\).
Например, если \(n=4\) и \(a=[4, 5, 2, 5]\), тогда Поликарп мог сделать следующее:
- Поликарп выбирает \(k=2\) друзей с номерами \(i=[2, 4]\) и перераспределяет \(a_2 + a_4 = 10\) конфет так, что в итоге \(a=[4, 4, 4, 4]\) (две конфеты достаются человеку под номером \(3\)).
Заметьте, что в данном примере Поликарп не может выбрать \(k=1\) друга так, чтобы можно было перераспределить конфеты так, что в итоге все \(a_i\) равны между собой.
Для данных \(n\) и \(a\) определите минимальное значение \(k\). При этом значении \(k\) Поликарп должен иметь возможность выбрать \(k\) друзей и перераспределить их конфеты так, что у всех в итоге будет одинаковое количество конфет.