Find the Majority Element

Mediumjavapythonccppjavascript

Given an array of size N, find the element that appears more than N/2 times. You may assume a majority element always exists.

Input Format

The first line contains an integer N. The second line contains N space-separated integers.

Output Format

Print the majority element.

Example 1

Input

3
2 1 2

Output

Explanation: 2 appears 2 times, which is greater than floor(3/2) = 1.

Run your code to see output here...