Majority Element

Given an array of integers, find the majority element. The majority element is defined as the element that appears more than \(\lfloor \frac{n}{2} \rfloor\) times, where \(n\) is the number of elements in the array.

You are guaranteed that the majority element always exists.

Example:

• For the input array [1, 2, 3, 2, 2], the output should be 2.

inputFormat

The first line of input contains a single 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.

5
1 2 3 2 2

2