题目描述

在一家大型餐厅里，有 $N$ 位常客（$2\le N\le 10^5$），他们被编号为 $1$ 到 $N$。每位常客都有自己特别喜欢的一种菜品口味 $h_i$（$1\le h_i\le N$）。

餐厅的老板希望所有的常客都能喜欢同一种菜品口味，这样在采购食材和制定菜单时就能更加方便和高效。

为了实现这个目标，老板可以组织试吃活动。一次试吃活动会邀请编号从 $i$ 到 $j$ 的连续范围内的所有常客参加。如果在试吃活动中，有一种菜品口味是小组中超过一半的常客喜欢的，那么在这次试吃活动结束后，该小组内的所有常客最终都会喜欢这种菜品口味。如果不存在这样的菜品口味，那么常客们的口味偏好将保持不变。

例如，在一个由 $16$ 位常客组成的试吃活动中，需要有其中 $9$ 名或更多的常客喜欢同一种菜品口味，才能使其余常客改变他们的喜好以与之一致。

老板想知道，哪些类型的菜品口味有可能最终让所有的常客都喜欢。老板为了达到所有常客都喜欢同一种菜品口味的目标，他可以根据需要任意多次地组织试吃活动。

输入格式

从文件 $eat.in$ 中读入数据。

输入的第一行包含一个整数 $T$，为独立的测试用例的数量（$1\le T\le 10$）。

每一个测试用例的第一行包含 $N$。

第二行包含 $N$ 个整数，为常客们喜爱的菜品口味$h_i$。

输入保证所有测试用例的 $N$ 之和不超过 $2\cdot 10^5$。

输出格式

输出答案到文件 $eat.out$ 中。

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

如果可能使所有常客同时喜欢同一种菜品口味，则以升序输出所有可能的菜品口味，否则输出 $-1$。

在同一行内输出一列整数时，相邻的数用空格分隔，并确保行末没有多余空格。

输入输出样例 #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

输出 #1

2
-1
1 2
3
-1

样例1解释

在输入样例中，有 5 个测试用例。

在第一个测试用例中，仅可能使所有常客喜欢菜品口味 $2$。餐厅的老板可以通过组织一次所有常客的试吃活动来达到一目的。

在第二个测试用例中，可以证明没有常客会改变她们喜爱的干草种类。

在第三个测试用例中，有可能使所有常客喜欢菜品口味 $1$，可以通过组织三次试吃活动来达到这一目的——首先使常客 $1$ 到 $4$ 进行一次试吃活动，随后使常客 $1$ 到 $5$ 进行一次试吃活动，随后使常客 $1$ 到 $6$ 进行一次试吃活动。以类似的逻辑，依次操作常客 $3$ 到 $6$，随后是常客 $2$ 到 $6$，随后是常客 $1$ 到 $6$，我们可以使所有常客喜欢菜品口味 $2$。

在第四个测试用例中，有可能使所有常客喜欢菜品口味 $3$，可以通过主持一次所有常客的试吃活动来达到这一目的。

在第五个测试用例中，可以证明没有常客会改变她们喜爱的菜品口味。

测试点性质

• 测试点 $2$：$N=2$。
• 测试点 $3-4$：$N\le 50$。
• 测试点 $5-6$：对于所有的 $1\le i\le N−1$，有 $h_i\le h_{i+1}$。
• 测试点 $7-15$：没有额外限制。

大样例下载