Majority Element

Given an unsorted array of integers, find the majority element. The majority element is the element that occurs more than \(\lfloor n/2 \rfloor\) times in the array.

You are guaranteed that the majority element exists in the array.

Example 1: For an input array [3, 2, 3], the output is 3.

Example 2: For an input array [2, 2, 1, 1, 1, 2, 2], the output is 2.

inputFormat

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

outputFormat

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

3
3 2 3

3