258. The Majority Element
Print the value that appears MORE than n/2 times among n integers, or
-1 if no value does.
Strictly more than half. In 1 1 2 2 neither value qualifies, because two is
not more than two.
Sorting gives a neat solution: if a majority exists it must occupy the middle
position, so check whether the value there actually appears often enough. That
is O(n log n).
There is also a beautiful O(n) solution using no extra memory. Pair off
values that differ, and anything left standing at the end is the only possible
majority. It still needs verifying, which is why the last step is a count.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ a[i] ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print the majority value, or -1 if none appears more than n/2 times.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.