Majority Element Finder

You are given an array of integers. The majority element is the element that appears more than (\lfloor \frac{n}{2} \rfloor) times (i.e. strictly more than half of the total number of elements). Your task is to determine this majority element. If there is no such element, output -1.

Note: The threshold is computed as (\lfloor \frac{n}{2} \rfloor), where (n) is the number of elements in the array.

inputFormat

The first line of input contains a single integer (n), representing the size of the array. The second line contains (n) space-separated integers.

outputFormat

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

9
3 3 4 2 4 4 2 4 4

4