Find the Special Element

You are given a list of integers. Your task is to find an element that appears strictly more than \(\lfloor n/3 \rfloor\) times in the list, where \(n\) is the number of elements in the list. If such an element exists, print it; otherwise, print \(-1\).

For example, in the array [3, 2, 3], the element 3 appears twice, which is more than \(\lfloor 3/3 \rfloor = 1\), so the answer is 3. In the array [1, 2, 3], no element appears more than \(\lfloor 3/3 \rfloor = 1\) times, so the answer is \(-1\).

inputFormat

The first line of input contains an integer \(n\), the number of elements in the list. The second line contains \(n\) space-separated integers representing the elements of the list.

outputFormat

Output a single integer which is the element that appears more than \(\lfloor n/3 \rfloor\) times. If no such element exists, output \(-1\).

3
3 2 3

3