Find the Majority Element

You are given an array of integers with a guaranteed majority element; that is, one element appears more than \(\lfloor n/2 \rfloor\) times. Your task is to find and output this majority element.

Explanation: A majority element in an array of size \(n\) is an element that appears more than \(n/2\) times. It is guaranteed that such an element exists in the input.

For example, in the array [3, 2, 3], the number 3 is the majority element since its frequency (2) is more than \(3/2 = 1.5\).

inputFormat

The input is read from stdin and has the following format:

n
x1 x2 x3 ... xn

Here, n is the number of elements in the array, and x1, x2, ..., xn are the integers in the array.

outputFormat

Output the majority element to stdout.

Note: Do not print any extra spaces or newlines.

3
3 2 3

3