Majority Element

Given an array of integers of length \(n\), where the majority element (the element that appears more than \(\lfloor n/2 \rfloor\) times) is guaranteed to exist, your task is to find and output the majority element.

You are encouraged to use the Boyer-Moore Majority Vote algorithm, which works in \(O(n)\) time and \(O(1)\) extra space.

inputFormat

The first line contains a single integer \(n\) (\(1 \leq n \leq 10^5\)), the number of elements in the array.

The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single integer, which is the majority element of the array.

## sample

6
3 1 3 3 2 3

3

</p>