题意

农夫约翰有一项重要的任务——弄清楚要为他的奶牛们购买什么类型的干草。

农夫约翰的 N
头奶牛编号为 1
到 N
，每头奶牛喜欢恰好一种类型的干草 hi
。

他希望他的所有奶牛都喜欢同一种干草。

为了实现这一目标，农夫约翰可以主持焦点小组访谈。

每一次焦点小组访谈，约翰都可以自由选择任意多个连续编号的奶牛构成访谈小组，共同参加访谈。

如果有一种干草是小组中超过一半的奶牛喜欢的，则此次焦点小组访谈结束后，组内所有奶牛最终都会喜欢这种干草。

如果不存在这样的干草，那么奶牛们就不会改变她们喜欢的干草类型。

例如，在由 16
头奶牛组成的焦点小组访谈中，需要有其中 9
头或更多的奶牛具有相同的干草喜好，才能使其余奶牛改变其喜好以与之一致。

农夫约翰想知道哪些类型的干草有可能变为同时受到所有奶牛的喜爱。

他一次只能主持一个焦点小组访谈，但为了使所有奶牛都喜欢同一类型的干草，他可以根据需要任意多次地主持焦点小组访谈。

思路

连续两个出现必定符合条件，但是观察样例：

3 2 3

也能符合，因此当考虑不连续的情况：

• 当连续段为偶数时，若要大于1/2，必定存在数字连续两次出现

• 当连续段为奇数时，若要大于1/2，当段内数字都不连续时，必定需要满足形如3 2 3的形式

因此只需要考虑距离为2内是否有相同数字

时间复杂度

O(n)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int t;
int n;
int a[N];
set<int>s;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        s.clear();
        memset(a,0,sizeof(a));
        cin>>n;
        for(int i=1;i<=n;i++)
        cin>>a[i];
        for(int i=1;i<n;i++)
        if(a[i]==a[i+1]||a[i]==a[i+2])s.insert(a[i]);
        if(s.size()==0)cout<<-1;
        else {
            for(auto e:s)cout<<e<<' ';
        }
        cout<<'\n';
    }
    return 0;
}