#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long int
#define endl '\n'
#define all(v) v.begin(), v.end()
#define pb push_back //
#define fi first //
#define se second //
#define yes cout << "YES" << endl //
#define no cout << "NO" << endl //
#define M 1000000007 // 1e9+7
#define gcd(a, b) __gcd(a, b) //
#define lcm(a, b) a *b / gcd(a, b) //
#define memz(a) memset(a, 0, sizeof(a)) //
#define memn(a) memset(a, -1, sizeof(a)) //
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key
ll block=500;
struct query
{
ll l,r,i;
bool operator <(query b)
{
if(this->l/block!=b.l/block)return this->l/block<b.l/block;
else return this->r<b.r;
}
};
map<ll,ll>coun;
ll mp[300010];
pbds x;
ll l,r;
void add(ll val)
{
if(mp[val])x.erase(x.find({mp[val],val}));
mp[val]++;
x.insert({mp[val],val});
}
void remove(ll val)
{
if(mp[val])x.erase(x.find({mp[val],val}));
mp[val]--;
if(mp[val])x.insert({mp[val],val});
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll n,q;
cin>>n>>q;
ll arr[n+1];
for(int i=1;i<=n;i++)cin>>arr[i];
query qu[q];
for(int j=0;j<q;j++)
{
cin>>qu[j].l>>qu[j].r;
qu[j].i=j;
}
sort(qu,qu+q);
ll ans[q];
ll l=1,r=0;
for(int i=0;i<q;i++)
{
ll s=qu[i].l;
ll e=qu[i].r;
ll j=qu[i].i;
while(e>r)
{
r++;
add(arr[r]);
}
while(s<l)
{
l--;
add(arr[l]);
}
while(e<r)
{
remove(arr[r]);
r--;
}
while(s>l)
{
remove(arr[l]);
l++;
}
ll out=INT_MAX;
for(int i=x.size()-1;i>=0;i--)
{
pair<ll,ll>p=*x.find_by_order(i);
if(p.first>(r-l+1)/3)
{
out=min(out,p.second);
}
else
{
break;
}
}
if(out==INT_MAX)ans[j]=-1;
else ans[j]=out;
}
for(int i=0;i<q;i++)cout<<ans[i]<<endl;
}