Majority Element

Given an array of n integers, it is guaranteed that one element (called the majority element) appears more than \(\lfloor n/2 \rfloor\) times. Your task is to find and output this majority element.

It is guaranteed that the majority element exists in the input array.

Note: Read the input from standard input (stdin) and write the output to standard output (stdout).

inputFormat

The first line of input contains an integer n, the number of elements in the array. The second line contains n space-separated integers.

Example:

3
3 2 3

outputFormat

Output a single integer — the majority element.

3
3 2 3

3