Majority Element

You are given n positive integers \(a_i\). It is guaranteed that there exists an element (the majority element) that appears more than \(\frac{n}{2}\) times. Your task is to find and output this majority element.

Note: You can assume that the majority element always exists in the input.

inputFormat

The first line of input contains a single integer \(n\), representing the number of elements.

The second line contains \(n\) positive integers \(a_1, a_2, \ldots, a_n\) separated by spaces.

outputFormat

Output the majority element, which is guaranteed to appear more than \(\frac{n}{2}\) times.

sample

5
2 2 1 2 2

2