Новый русский Колян любит две вещи: деньги и порядок. У Коляна много денег, но в них нет порядка. Одним прекрасным утром Колян понял, что он больше не может это переносить, и решил навести порядок в своих деньгах. Он приказал своим верным помощникам извлечь деньги из подземного хранилища, и скоро его большая комната была заполнена красными, зелёными и синими банкнотами. Колян смотрел с отвращением на этот ужасный беспорядок. Сейчас он хочет оставить в своём хранилище банкноты только одного достоинства, а остальные деньги раздать бедным. Он точно знает, что более половины банкнот имеют одинаковое достоинство. Но в беспорядке невозможно понять, какая банкнота встречается чаще всего.
Исходные данные
Первая строка содержит количество банкнот Коляна N (1 ≤ N ≤ 500 000). В следующих N строках даны достоинства K этих банкнот (0 ≤ K ≤ 109). Более половины из этих значений одинаковы.
Результат
Выведите наиболее часто встречающееся достоинство банкнот.
Пример
исходные данные | результат |
---|
5
3
3
2
2
3 | 3 |
Автор задачи: Ден Расковалов
Источник задачи: Quarter-Final of XXXI ACM ICPC - Yekaterinburg - 2006