Majority Element

Medium#arrays #boyer-moore #hashing· solved by 0 · time limit 2.0 s

Print the value that appears more than $n/2$ times, or -1 if none does. (The Boyer–Moore voting algorithm needs only $O(1)$ extra memory.)

Input

$n$ , then $n$ integers.

The majority value or -1.

$1 \le n \le 10^5$

Input

7
2 2 1 1 1 2 2

Output

Input

2
1 2

Output

-1