Ktulu
Limit pamięci: 128 MB
Bajtazar jest opiekunem na obozie informatycznym i umówił się z jego uczestnikami na 20:30 na grę w Ktulu.
Punktualnie o 20:30 w umówionym miejscu zjawiła się liczna grupa chętnych i wygląda na to, że jest ich zbyt wielu,
by wszyscy wzięli udział w jednej grze.
W tej sytuacji Bajtazar postanowił podzielić uczestników na grupy.
W Ktulu chce grać uczestników, których numerujemy od do .
Każdy uczestnik ma pewne preferencje dotyczące tego, jak powinna wyglądać gra w Ktulu.
Konkretnie, dla każdego uczestnika znamy liczbę całkowitą , która oznacza, że
uczestnik ten chciałby znaleźć się w grupie składającej się z lub graczy.
Bajtazar chciałby teraz sprawdzić, czy chętnych do gry da się podzielić na grupy
zgodnie z ich wymaganiami, tak by każdy uczestnik należał do dokładnie jednej grupy.
Jeśli jest to możliwe, Bajtazar chciałby znaleźć podział na jak największą liczbę grup.
Pomóż Bajtazarowi i napisz program, który rozwiąże jego problem.
Wejście
Pierwszy wiersz wejścia zawiera liczbę całkowitą
() oznaczającą liczbę chętnych do gry w Ktulu.
Drugi wiersz zawiera ciąg liczb całkowitych (), które oznaczają
preferencje poszczególnych uczestników.
Wyjście
Twój program powinien wypisać jedną liczbę całkowitą.
Jeśli uczestników da się tak podzielić na grupy, by uczestnik
należał do grupy o rozmiarze
lub
, wypisz
maksymalną możliwą liczbę grup w takim podziale.
W przeciwnym razie, na wyjście należy wypisać
.
Przykład
Dla danych wejściowych:
7
3 1 3 2 1 3 2
poprawną odpowiedzią jest:
4
Autor zadania: Adam Karczmarz.