Majority Element Finder

In this problem, you are given an array of integers. Your task is to find the majority element in the array, which 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. If no such element exists, output -1. The intended solution uses the Boyer-Moore Voting Algorithm.

inputFormat

The input is given via standard input (stdin). The first line contains a single integer (n) ((n \ge 0)) representing the number of elements in the array. The second line contains (n) space-separated integers.

outputFormat

Output the majority element if it exists; otherwise, output -1. The result should be printed to standard output (stdout).## sample

7
1 1 1 1 2 3 4

1