Najčešći

Potrebno je pronaći element koji se javlja bar pola puta od ukupnog broja elemenata. Dodatna prostorna složenost treba da bude \(O(1)\).

Opis ulaza

Sa standarnog ulaza se zadaje broj \(n\) (\(1 \leq n \leq 10^5\)), a potom i \(n\) pozitivnih celih brojeva.

Opis izlaza

Na standardni izlaz ispisati element koji se javlja bar \(n/2\) puta, ili \(-1\) ako takav element ne postoji.

Primer 1

Ulaz

7
1 2 1 2 1 1 3

Izlaz

1

Primer 2

Ulaz

7
1 2 1 2 4 1 3

Izlaz

-1