Majority Element Finder

You are given an array of n integers. Your task is to find the majority element in the array. An element is considered a majority if it appears more than $$\frac{n}{2}$$ times. If no such element exists, print -1.

This problem can be efficiently solved using the Boyer-Moore Voting Algorithm. The input will be read from stdin and the result should be printed to stdout.

inputFormat

The first line of the input contains an integer n representing the number of elements in the array.

The second line contains n space-separated integers, which are the elements of the array.

outputFormat

Output a single integer which is the majority element if it exists; otherwise, output -1.

9
3 3 4 2 4 4 2 4 4

4