Rezolvare PBinfo #1754

Vrăjitorul Arpsod își dorește să își reamenajeze habitatul. În habitatul acestuia există N munți, fiecare cu o înălțime cunoscută. Fiind un tip cu un foarte dezvoltat simț estetic, el își dorește să remodeleze cei N munți astfel încât să obțină un număr maxim de munți cu aceeași înălțime.

Arpsod are la îndemână o magie ce funcționează astfel: alege oricare doi munți, pe primul îl crește cu o unitate iar pe al doilea îl scade cu o unitate. Un munte poate ajunge la înălțimi negative ( practic se transformă într-o groapă ).

Arpsod își poate folosi magia de un număr infinit de ori.

Cerința

Vrăjitorul vă cere să determinați numărul maxim de munți ce pot fi aduși la o înălțime egală.

Date de intrare

Pe prima linie a fișierului munti.in se va afla numărul natural N, reprezentând numărul de munți existenți. Pe cea de-a doua linie se vor afla N valori naturale separate prin spațiu, reprezentând înălțimea inițială a fiecărui munte.

Date de ieșire

Fișierul munti.out va conține, pe prima și singura linie a fișierului, numărul maxim de munți ce pot fi aduși la o înălțime egală.

Restricții și precizări

• 1 ≤ N ≤ 1.000.000
• 1 ≤ înălțimea inițială ≤ 1.000.000.000

Exemplu:

munti.in

4
2 6 2 2

munti.out

4

Explicație

Toți munții pot fi aduși la înălțime 3, la fiecare pas scădem o unitate din muntele de înălțime 6 și adăugăm la un munte de înălțime 2.