Majority Element (>N/2 times)

Majority Element (>N/2 times)

Find the element that appears more than N/2 times in an array using Boyer-Moore voting.

Input format

The first line contains N. The second line contains N integers. A majority element (appearing more than N/2 times) is guaranteed to exist.

Output format

Print the majority element.

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.

3
3 2 3

3

7
2 2 1 1 1 2 2

2