POLSKI SPOJ

Danych jest n liczb naturalnych. Twoim zadaniem jest znaleźć liczbę, która występuje więcej niż n/2 razy w podanym zestawie liczb. Jeśli takiej nie ma, na wyjściu program powinien wypisać wartość -1.

Wejście

W pierwszej linii wejścia znajduje się liczba testów t (t ≤ 10).  Następnie t testów. Każdy z nich zaczyna się od liczby n (1 ≤ n ≤ 5*10⁵), która określa ilość liczb do wczytania. Następnie n liczb a_i (0 ≤ a_i ≤ 10¹⁸).

Wyjście

Wartość liczby a_i, która występuje w ciągu więcej niż n/2 razy lub -1 jeśli takiej liczby nie ma.

Wejście:
4
2
10
20
3
10
10
20
1
1
2
2
2

Wyjście:
-1
10
1
2