Majority Element Finder

You are given an array of integers. Your task is to find the majority element in the array. A majority element is defined as an element that appears more than \(\frac{n}{2}\) times, where \(n\) is the number of elements in the array.

If such an element exists, print it. Otherwise, print "None".

Note: The input and output must be handled using standard input (stdin) and standard output (stdout), respectively.

inputFormat

The first line 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 it exists; otherwise, print "None".

## sample

9
3 3 4 2 4 4 2 4 4

4

</p>