Majority Element

Given an array of integers, determine its majority element — the element that appears more than \( n/2 \) times, where \( n \) is the size of the array. If no such element exists, output \(-1\).

The input is provided via standard input (stdin) and the output should be printed to standard output (stdout).

inputFormat

The first line contains an integer \( n \) representing the number of elements in the array. If \( n > 0 \), the second line contains \( n \) space-separated integers. If \( n = 0 \), no further input is provided.

outputFormat

Output a single integer — the majority element if it exists; otherwise, output \(-1\).

9
3 3 4 2 4 4 2 4 4

4