У Фермера Джона важная задача - решить какой тип сена купить для своих коров.
У Фермера Джона есть \(N\) коров (\(2 \le N \le 10^5\)) пронумерованных
от \(1\) до \(N\). Каждая корова любит ровно один тип сена \(h_i\) (\(1 \le h_i \le N\)).
ФД хочет, чтобы все его коровы любили один тип сена.
Чтобы это случилось, ФД может сформировать фокус-группы. Фокус-группа состоит
из всех коров в непрерывном интервале от \(i\) до \(j\), включительно. Если в
фокус-группе более половины коров любит один и тот же некоторый тип сена,
то все коровы начинают любить этот тип сена, иначе ни у одной коровы не
изменяется любимый тип сена. Например, если фокус группа состоит из 16 коров,
9 или более из которых любят один и тот же тип сена, то и остальные 7 коров
теперь будут любить этот же тип сена.
ФД хочет узнать, какие типы сена могут стать любимыми всем коровами.
В один момент времени он может создать только одну фокус группу, но он может
последовательно создавать сколько угодно фокус-групп, чтобы все коровы
полюбили один и тот же тип сена.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Сначала идёт одно целое число \(T\), которое обозначает количество независимых
тестов \((1 \leq T \leq 10)\).
Первая строка каждого теста содержит число \(N\).
Вторая строка каждого теста состоит из \(N\) целых чисел, любимых типов
сена \(h_i\), в порядке номеров коров.
Гарантируется, что сумма \(N\) во всех тестах не превысит \(2\cdot 10^5\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите
\(T\) строк, по одной для каждого теста.
Если возможно сделать, чтобы все коровы полюбили один и тот же тип сена,
выведите все такие возможные типы сена в порядке возрастания. Иначе, выведите
\(-1\).
Когда выводите список чисел, выводите соседние числа через один пробел,
и в конце этой строки не должно быть пробелов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5
1 2 2 2 3
6
1 2 3 1 2 3
6
1 1 1 2 2 2
3
3 2 3
2
2 1
|
2
-1
1 2
3
-1
|