Majority Element

You are given an array of integers. The task is to determine if there is a majority element in the array. A majority element is defined as an element that appears more than \(n/2\) times, where \(n\) is the total number of elements in the array.

If a majority element exists, output that element; otherwise, output \(-1\). An efficient solution can be achieved using the Boyer-Moore Voting Algorithm.

Example:

• Input: 7 (number of elements) and 3 3 4 2 4 4 4
• Output: 4 because the integer 4 appears 4 times which is more than \(7/2 = 3.5\).

inputFormat

The input consists of two lines. The first line contains a single integer (n) denoting 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 if it exists, otherwise output (-1).## sample

7
3 3 4 2 4 4 4

4