Зачаровані музичні скриньки#4223
Ліра, мандрівна бард, щойно отримала великий ящик, наповнений зачарованими музичними скриньками, від Майстра Мелодіуса, відомого магічного ремісника. Коли вона відкрила ящик, десятки чудово оздоблених скриньок висипалися разом із листом:
Дорога Ліро,
Сподіваюся, ці зачаровані музичні скриньки принесуть радість твоїм виступам. Перепрошую за безлад — у мене не вистачило часу, щоб правильно їх організувати перед твоїм від'їздом. Кожна скринька наділена просторовою магією: ти помітиш, що менші скриньки можна поміщати в більші, де вони ідеально вміщуються і продовжують відтворювати свої мелодії в гармонії.
Нехай твої пісні чарують королівство,
Майстер Мелодіус
Мандрівний візок Ліри вже переповнений музичними інструментами та магічними артефактами. Щоб заощадити цінний простір, вона вирішує оптимально вкласти скриньки одну в одну, мінімізуючи кількість найзовнішніх скриньок.
Кожна зачарована музична скринька має унікальний розмір, представлений одним числом s_i, що позначає її розміри. Скринька може поміститися в іншу скриньку тоді і тільки тоді, коли s_i < s_j. Через природу просторових чарів кожна скринька може містити не більше однієї іншої скриньки безпосередньо всередині (хоча внутрішня скринька може сама містити іншу, створюючи вкладений ланцюжок).
Поки Ліра організовує свою колекцію зачарованих музичних скриньок, чи можете ви допомогти їй визначити мінімальну кількість найзовнішніх скриньок, необхідних для її воза?
Вхідні дані складаються з кількох тестів. Кожен тест починається з рядка з цілим числом (1 \leq N \leq 10^5), що позначає кількість зачарованих музичних скриньок. Далі йдуть рядків, кожен з одним цілим числом s_i (1 \leq s_i \leq 10^9), що позначає розмір -ї музичної скриньки. Вхідні дані завершуються рядком з N = 0, який не слід обробляти.
Для кожного тесту виведіть один рядок з цілим числом, що представляє мінімальну кількість найзовнішніх скриньок, яку можна отримати, оптимально вклавши зачаровані музичні скриньки.
Приклад 1