题目描述

给定一个长度为 $n$ 的序列 $a$。

一次操作可以选择一个连续子区间 $[l,r]$。设这个区间内某个数 $x$ 的出现次数严格大于区间长度的一半，那么执行这次操作后，区间 $[l,r]$ 中的所有数都会变成 $x$。如果不存在这样的数，则这次操作不会产生任何变化。

你可以进行任意多次操作，每次只选择一个区间。

对于每个测试用例，求哪些数有可能通过若干次操作后，使整个序列所有元素都变成这个数。

输入格式

第一行一个整数 $t$，表示测试用例组数。

对于每个测试用例：

• 第一行一个整数 $n$。
• 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

保证所有测试用例的 $n$ 之和不超过 $2\times 10^5$。

输出格式

对于每个测试用例输出一行。

若存在若干个数可以最终把整个序列变成它们之一，则按升序输出所有这样的数，相邻两个数之间用一个空格隔开。

如果不存在这样的数，输出 $-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

样例解释

第 1 组

序列为：$1\ 2\ 2\ 2\ 3$

可以选择整个区间 $[1,5]$，其中数字 $2$ 出现了 $3$ 次，超过区间长度的一半，因此一次操作后整个序列变为：

$$2\ 2\ 2\ 2\ 2$$

所以答案为 $2$。

---

第 2 组

序列为：$1\ 2\ 3\ 1\ 2\ 3$

任意区间内都不存在某个数出现次数严格超过一半，因此无法进行有效改变。

答案为 $-1$。

---

第 3 组

序列为：$1\ 1\ 1\ 2\ 2\ 2$

可以通过多次操作逐步扩展：

例如可以不断选择包含多数的区间，将某个数向外“扩散”，最终可以把整个序列变为 $1$；同理也可以全部变为 $2$。

因此答案为：

$$1\ 2$$

---

第 4 组

序列为：$3\ 2\ 3$

区间 $[1,3]$ 中，数字 $3$ 出现了 $2$ 次，超过一半，因此可以一次操作变为：

$$3\ 3\ 3$$

答案为 $3$。

---

第 5 组

序列为：$2\ 1$

长度为 $2$ 的区间需要某个数出现至少 $2$ 次才算超过一半，但两个数不同，因此无法操作。

答案为 $-1$。

---

测试点性质

• 测试点 $2$：$n=2$
• 测试点 $3\sim4$：$n \le 50$
• 测试点 $5\sim6$：序列单调不下降（即 $a_i \le a_{i+1}$）
• 测试点 $7\sim15$：无额外限制