Element with large number of occurrence

Ninja gets very irritated when he finds duplicate elements with large number of occurrences in an array, say 'ARR' of 'N' integers. He wants to find the element with large number of occurrences in the array so that he can remove that element later from that array.

Ninja asks for your help to find such element from the array. Help Ninja!

Note:

An element is having large number of occurrence if that element occurs more than floor('N' / 2) times in the array. If there is no such element present, print -1.

Input Format:

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains a single positive integer ‘N’ representing the size of the array/list.

The second line of each test case contains ‘N’ single space-separated integers representing the array elements of 'ARR'.

Output Format :

For each test case, print an integer denoting the majority element present in the array. Print-1 in case of no majority element.

Note :

You don't need to print the output, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 5 * 10^3
-10^5 <= ARR[i] <= 10^5

Where 'ARR[i]' denotes the element at the 'i'th index in the array/list 'ARR'.

Time limit: 1 sec