Wyszukiwanie lidera

Limit czasu: 1s | Limit pamięci: 64MB

Dany jest ciąg $a_1, a_2, \ldots, a_n$. Znajdź element tego ciągu, który występuje w nim więcej niż $n/2$ razy. Element taki nazywamy liderem ciągu.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę $n$. Drugi wiersz zawiera $n$ liczb $a_i$.

Wyjście

Pierwszy i jedyny wiersz wyjścia zawiara wartość lidera. Jeśli ciąg nie posiada lidera, wypisz napis BRAK

Ograniczenia

• $1 \le n \le 10^6$
• $-10^9 \le a_i \le 10^9$

Przykłady

Wejście 1

5
1 3 1 3 1

Wyjście 1

1

Wejście 2

6
1 1 1 3 3 3

Wyjście 2

BRAK