Majority ElementEasy

Majority Element

Easy+5 XP · +3 Aura (late, half)arrayscounting

In an array of n integers one value appears more than n / 2 times. Print that value.

It is guaranteed that such a value exists. Aim for O(n) time; the arrays are big.

Input

Line 1: n Line 2: n integers

Output

The majority value.

Constraints

  • 1 <= n <= 500000
  • |value| <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB8 hidden tests

Example 1

Input
3
3 2 3
Output
3

Example 2

Input
7
2 2 1 1 1 2 2
Output
2

2 appears 4 times out of 7.

Hints