Problem description
Krasnal Bitek dostał właśnie nową pracę w technologicznej korporacji Facebajt. Jako menedżer ma pod swoją opieką N zespołów programistycznych, liczących odpowiednio A1, A2, …, AN osób.
W ramach firmowej restrukturyzacji Bitek może wielokrotnie wybrać dwa zespoły liczące x oraz y pracowników i połączyć je w jeden nowy zespół liczący x + y osób. Każda taka operacja zmniejsza łączną liczbę zespołów o 1.
Zbliża się koniec kwartału i Bitek musi przygotować raport. Aby statystyki ładnie prezentowały się przed zarządem, średnia liczba osób w zespole po wszystkich połączeniach musi być liczbą całkowitą.
Jaka jest minimalna liczba połączeń zespołów, które Bitek musi wykonać, aby osiągnąć ten cel? Można pokazać, że osiągnięcie tego celu jest zawsze możliwe.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę naturalną N.
Drugi wiersz wejścia zawiera N liczb naturalnych A1, A2, …, AN, oddzielonych pojedynczymi odstępami, oznaczających liczbę osób w kolejnych zespołach.
Wyjście
Na wyjściu wypisz jedną liczbę całkowitą: minimalną liczbę połączeń, które musi wykonać Bitek.
Ograniczenia
1 ≤ N ≤ 106, 1 ≤ Ai ≤ 1000.
Przykłady
| Wejście | Wyjście | Wyjaśnienie |
|
|
Średnia już wynosi 1, więc Bitek nie musi nic robić. |
| Wejście | Wyjście | Wyjaśnienie |
|
|
Aktualnie średnia wynosi $5\frac{1}{3}$. Bitek może połączyć zespoły o 3 i 5 osobach i dostać dwa 8-osobowe zespoły. Wtedy średnia wynosi 8 i jest już liczbą całkowitą. |
| Wejście | Wyjście | |
|
|