Find the Majority Element

Given an array of integers, your task is to determine if there exists a majority element in the array. An element is considered a majority element if it appears strictly more than (\frac{n}{2}) times in the array, where (n) is the total number of elements. If a majority element exists, output that element; otherwise, output -1.

The input will be provided via standard input, and you are expected to print the answer to standard output.

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.

outputFormat

Print the majority element if one exists; otherwise, print -1.## sample

5
3 3 4 2 3

3