Majority Element

You are given an array of integers. Your task is to find the majority element in the array. The majority element is the element that appears more than \(\frac{n}{2}\) times, where \(n\) is the number of elements in the array. If no such element exists, output \(-1\).

For example:

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

inputFormat

The input is given via standard input (stdin) and consists of two lines:

1. The first line contains an integer \(n\) which represents the number of elements in the array. \(n\) can be zero.
2. The second line contains \(n\) space-separated integers representing the elements of the array. If \(n = 0\), the second line may be empty.

outputFormat

Output to standard output (stdout) a single integer, which is the majority element if one exists, or \(-1\) otherwise.

9
3 3 4 2 4 4 2 4 4

4