P10662: 少数服从多数
传统题
1.000s
时间限制
128MB
内存限制
1 提交
1 解决
【题目描述】
【题目描述】
Farmer John 有一项重要的任务——弄清楚要为他的奶牛们购买什么类型的干草。
Farmer John 的N头奶牛（2≤N≤10
5）编号为1
到 N，每头奶牛恰好
喜欢一种类型的干草 hi（1≤hi≤N）。他希望他的所有奶牛都喜欢同一种干草。
为了实现这一目标，Farmer John 可以主持焦点小组访谈。一次焦点小组访谈为让编号从i到j的连续范围内的所有奶牛聚集在一起参加一次访谈。如果有一种干草是小组中超过一半的奶牛喜欢的，则此次焦点小组访谈结束后，所有奶牛最终都会喜欢这种干草。如果不存在这种类型的干草，那么奶牛们不会改变她们喜欢的干草类型。例如，在由 16 头奶牛组成的焦点小组访谈中，需要有其中 9 头或更多的奶牛具有相同的干草喜好，才能使其余奶牛改变其喜好以与之一致。
Farmer John 想知道哪些类型的干草有可能变为同时受到所有奶牛的喜爱。他一次只能主持一个焦点小组访谈，但为了使所有奶牛都喜欢同一类型的干草，他可以根据需要任意多次地主持焦点小组访谈。
【输入格式】：
输入的第一行包含一个整数 T，
表示有T组测试用例（1≤T≤10）。
每一个测试用例的第一行包含 N，
表示有N个奶牛。
第二行包含N个整数，表示
奶牛们喜爱的干草类型 hi。
输入保证所有测试用例的N之和不超过 2⋅10
5。
【输出格式】：
输出T行，每个测试用例输出一行。
如果可能使所有奶牛同时喜欢同一种干草，则以升序输出所有可能的此类干草的类型，否则输出 −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
【样例说明】
在输入样例中，有 5 个测试用例。
在第一个测试用例中，仅可能使所有奶牛喜欢种类 2。FJ 可以通过主持一次所有奶牛的焦点小组访谈达到这一目的。
在第二个测试用例中，可以证明没有奶牛会改变她们喜爱的干草种类。
在第三个测试用例中，有可能使所有奶牛喜欢种类 1，可以通过主持三次焦点小组访谈达到这一目的——首先使奶牛 1 到 4 进行一次焦点小组访谈，随后使奶牛 1 到 5 进行一次焦点小组访谈，随后使奶牛 1 到 6 进行一次焦点小组访谈。以类似的逻辑，依次操作奶牛 3 到 6，随后是奶牛 2 到 6，随后是奶牛 1 到 6，我们可以使所有奶牛喜欢种类 2。
在第四个测试用例中，有可能使所有奶牛喜欢种类 3，可以通过主持一次所有奶牛的焦点小组访谈达到这一目的。
在第五个测试用例中，可以证明没有奶牛会改变她们喜爱的干草种类。
【数据约束】：
测试点 2：N=2。
测试点 3-4：N≤50。
测试点 5-6：对于所有的 1≤i≤N−1，有 hi≤hi+1。
测试点 7-15：没有额外限制。
【输入】
输入的第一行包含一个整数 T，表示有T组测试用例（1≤T≤10）。
每一个测试用例的第一行包含 N，表示有N个奶牛。
第二行包含N个整数，表示奶牛们喜爱的干草类型 hi。
输入保证所有测试用例的N之和不超过 2⋅105。
【输出】
输出T行，每个测试用例输出一行。
如果可能使所有奶牛同时喜欢同一种干草，则以升序输出所有可能的此类干草的类型，否则输出 −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