Найдите элемент, который встречается больше n/2 раз. Гарантируется, что такой есть. Бонус: O(1) памяти (алгоритм Бойера-Мура).