An array contains a majority element: a value that appears strictly more than n/2 times. It is guaranteed that such an element exists. Output it.
Input format
Line 1: an integer n.
Line 2: n space-separated integers.
Output format
One line: the majority element.
Constraints
- 1 <= n <= 100000
- -1000000000 <= each value <= 1000000000
- A value appearing more than n/2 times is guaranteed to exist.