🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新招商银行近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📧 清隆这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 清隆领取，会在飞书进行同步的跟新。

🏳️ 难难难！！！本次招商银行的笔试算是今年春招最难的场次之一了

K小姐所在的公司有NNN 个部门，编号从111 到NNN。由于公司网络系统比较老旧，对于同一个数据ddd，不同部门记录的值可能不同。数据ddd 在各部门被记录为d 1 ,d 2 ,...,d N d_1, d_2, ..., d_Nd1​,d2​,...,dN​。

公司提出可以通过会议来实现数据的一致性。每次会议会让相邻编号范围内的所有部门一起参加，如果有超过半数的部门能够对数据ddd 的值达成共识，那么在此次会议后，参与会议的所有部门会将数据更新为本次达成共识的值。如果会议内无法达成共识，相关部门均不会更新数据。

例如，如果有888 个部门参与了会议，那么需要有至少555 个部门达成共识，才能成功更新其他部门的数据。K小姐想知道有哪些数据值可能通过会议被所有部门接受，她一次只能组织一次会议，但是可通过任意多次组织会议来达成所有部门的数据一致性。

第一行包含整数TTT(1≤T≤20)(1 \leq T \leq 20)(1≤T≤20)，为测试用例的数量。

每一个测试用例的第一行包含整数NNN。

第二行包含NNN 个整数，为每个部门记录的数据ddd。

输入保证所有的测试用例的NNN 之和不超过3×10 5 3 \times 10^53×105。

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

如果可能实现所有部门的数据一致，则以升序输出所有可能的数据的值，否则输出−1-1−1。在同一行内输出数字时，相邻的值用空格分隔，需确保行末没有多余空格。

本题的思路是找出所有可能达成一致的数据值。我们可以发现，如果相邻的两个部门或者相隔一个部门的两个部门记录的数据值相同，那么这个数据值就有可能通过会议达成一致。

因此，我们可以遍历整个数组，统计所有相邻部门或者相隔一个部门的部门记录的相同数据值，将其加入到一个集合中。最后，如果集合为空，说明无法达成一致，输出−1-1−1；否则将集合中的元素升序输出即可。

时间复杂度为O(N)O(N)O(N)，空间复杂度为O(N)O(N)O(N)。