Majority Element Finder

You are given a list of integers. Your task is to determine if there exists an element in the list that appears more than \(\frac{n}{2}\) times (i.e. more than half of the total number of elements). If such an element exists, print that element; otherwise, print -1.

This problem can be solved using the Boyer-Moore Voting Algorithm. The algorithm works in two steps:

1. Find a candidate that might be the majority element.
2. Verify that the candidate appears more than \(\frac{n}{2}\) times.

Note: If there are no elements in the list, output -1.

inputFormat

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

• The first line contains an integer \(n\) representing the number of elements in the list.
• The second line contains \(n\) integers separated by spaces.

If \(n = 0\), the list is empty.

outputFormat

Output a single line to standard output (stdout) containing the majority element if it exists. Otherwise, print -1.

## sample

7
2 2 3 2 5 2 2

2

</p>