Problem description
N krasnali wybiera się na imprezę. Elementem stroju każdego krasnala jest szpiczasta czapka. We wspólnej garderobie krasnale zgromadziły N czapek. Każdy z nich założy na imprezę dokładnie jedną czapkę. Czapki są różnych długości od 1 do N i każda czapka trafi do dokładnie jednego krasnala.
i-ty krasnal ma wzrost Ai. Jeżeli i-ty krasnal założy czapkę o długości j, to jego sumaryczny wzrost będzie wynosił Ai + j. Krasnale mogą być różnego wzrostu, ale idąc na imprezę chciałyby wyglądać podobnie. W tym celu chcą rozdzielić czapki tak, aby jak najwięcej krasnali miało ten sam sumaryczny wzrost (wzrost krasnala powiększony o długość założonej czapki).
Twoim zadaniem jest napisanie programu, który obliczy i wypisze ile maksymalnie krasnali może mieć taki sam wzrost, po rozdzieleniu i założeniu czapek.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N – liczba krasnali. W drugim i ostatnim wierszu wejścia znajduje się N liczb całkowitych A1, A2, …, AN – wzrosty krasnali.
Wyjście
W pierwszym i jedynym wierszu wyjścia powinna się znaleźć jedna liczba całkowita – liczba krasnali, które mogą mieć równy wzrost, przy optymalnym rozłożeniu czapek.
Ograniczenia
1 ≤ N ≤ 106, 1 ≤ Ai ≤ 109.
Podzadania
| Podzadanie | Dodatkowe warunki | Punkty |
|---|---|---|
| 1 | n ≤ 9 | 10 |
| 2 | n ≤ 500 | 15 |
| 3 | Ai ≤ 106 | 20 |
| 4 | Liczby Ai są parami różne | 20 |
| 5 | brak | 35 |
Przykład
| Wejście | Wyjście | Wyjaśnienie |
|
|
Możemy przypisać kolejno czapki 6, 1, 5, 2, 4, 3, wtedy sumaryczne wzrosty wynoszą 13, 8, 13, 10, 13, 12 i krasnale 1, 3 i 5 są tego samego wzrostu. Nie da się uzyskać lepszego wyniku. |
| Wejście | Wyjście | |
|
|
| Wejście | Wyjście | |
|
|