Majority Element

Practice this coding question on Coding Gurukul.

Problem statement

A vote log contains one candidate with strictly more than half the votes. Recover that candidate identifier. The majority is guaranteed to exist, and identifiers may be negative. Aim for linear time and constant additional memory.

Input format

First line: n. Second line: n space-separated integers.

Output format

Print the majority value.

Constraints

1 <= n <= 100000; -1000000000 <= value <= 1000000000; a strict majority exists.

Sample input

5
4 1 4 2 4