Матрёшки
Адам только что получил коробку, полную матрёшек (традиционных русских кукол) от своей подруги Матрёны. Когда он открыл коробку, из неё высыпалось множество кукол вместе с запиской от неё:
Привет, Адам, надеюсь, тебе понравятся эти куклы. Но извини, у меня не было времени их рассортировать. Ты заметишь, что у каждой куклы есть полое отверстие внизу, которое позволяет вложить в неё куклу поменьше.
...
Твоя,
Матрёна
Адам, у которого уже так много вещей в его витрине, решает собрать кукол, чтобы уменьшить количество самых внешних кукол. Куклы, которые прислала Матрёна, имеют одинаковую форму, но разные размеры. То есть, кукла i может быть представлена одним числом h_i, обозначающим её высоту. Кукла i может поместиться в другую куклу j тогда и только тогда, когда h_i < h_j. Также куклы спроектированы так, что каждая кукла может содержать не более одной куклы внутри. Пока Адам складывает свою гигантскую коллекцию матрёшек, можете ли вы написать программу, чтобы вычислить минимальное количество самых внешних кукол, чтобы он мог понять, сколько места ему нужно в его витрине?
Входные данные
Входные данные состоят из нескольких тестов. Каждый тест начинается со строки с целым числом N, 1 ≤ N ≤ 10^5, обозначающим количество матрёшек. Далее следуют N строк, каждая с одним целым числом h_i, 1 ≤ h_i ≤ 10^9, обозначающим высоту i-й куклы в см. Входные данные завершаются строкой с N = 0, которая не должна обрабатываться.
Выходные данные
Для каждого теста выведите одну строку, содержащую целое число, представляющее минимальное количество самых внешних кукол, которые можно получить, оптимально сложив данные куклы.