Problem description

Jeżeli w danym ciągu a₁, …, a_n istnieje liczba, która występuje w nim więcej niż n/2 razy, to taką liczbę nazywamy liderem. Twoim zadaniem jest sprawdzać, czy dany ciąg ma lidera.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna t oznaczjąca liczbę zestawów testowych. Następnie dane jest t zestawów, każdy z nich następującej postaci. W pierwszym wierszu zestawu testowego podana jest jedna liczba naturalna n. W drugim wierszu zestawu testowego podane jest n liczb a₁, a₂, …a_n.

Wyjście

Dla każdego zestawu testowego należy wypisać wartość lidera tego ciągu lub  − 1 jeżli dany ciąg nie ma lidera.

Ograniczenia

W każdym zestawie testowym 1 ≤ n ≤ 500 000, 0 ≤ a_i ≤ 10¹⁸. Możesz założyć, że suma wartości n we wszystkich zestawach testowych nie przekracza 500 000.

Przykład

4
2
10 20
3
10 10 20
1
1 
2 
2 2

-1
10
1
2