Majority Element
Find the value that appears more than half the time.
Input format
The first line has N. The second line has N integers. A value appearing more than N/2 times is guaranteed to exist.
Output format
Print the majority element: the value that appears more than N/2 times.
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
5
3 3 4 2 3Expected output
3Example 2
Input
1
9Expected output
9