Majority Opinion

题目描述

农夫 John 有一项重要任务——弄清楚该给他的奶牛买哪一种干草。

农夫 John 有 $N$ 头奶牛（$2 \le N \le 10^5$），编号为 $1$ 到 $N$。每头奶牛恰好喜欢一种干草类型 $h_i$（$1 \le h_i \le N$）。他希望所有奶牛最终都喜欢同一种干草。

为此，农夫 John 可以举办焦点小组（focus group）。一次焦点小组是指让编号在连续区间 $i$ 到 $j$（含端点）内的所有奶牛聚在一起开会。如果在该小组中存在某一种干草类型，被超过一半的奶牛喜欢，那么会议结束后，小组内所有奶牛都会变得喜欢这一种干草类型。如果不存在这样的干草类型，则没有奶牛会改变自己喜欢的干草类型。例如，在一个包含 16 头奶牛的焦点小组中，至少需要 9 头奶牛有相同的干草偏好，才能使其余奶牛改为相同偏好。

农夫 John 想知道：哪些干草类型可以最终被所有奶牛同时喜欢。他一次只能举办一个焦点小组，但他可以举办任意多次焦点小组，以让所有奶牛都喜欢同一种干草。

输入格式

第一行是整数 $T$，表示相互独立的测试用例数量（$1 \leq T \leq 10$）。

每个测试用例的第一行包含 $N$。 第二行包含 $N$ 个整数，按顺序给出各头奶牛喜欢的干草类型 $h_i$。

保证所有测试用例的 $N$ 之和不超过 $2\cdot 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。 在第五个测试用例中，我们可以证明没有奶牛会改变自己喜欢的干草类型。 SCORING: Input 2: $N = 2$. Inputs 3-4: $N \le 50$. Inputs 5-6: $h_i \le h_{i+1}$ for all $1 \le i \le N-1$. Inputs 7-15: No additional constraints. Problem credits: Nick Wu

标签: USACO|2024|Bronze

来源

USACO|2024|Bronze