#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
struct query
{
ll l,r,i;
};
ll block=550;
bool cmp(query a,query b)
{
if(a.l/block!=b.l/block)return a.l/block<b.l/block;
else return a.r<b.r;
}
ll mp[200010];
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)
{
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,cmp);
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++;
}
// for(auto u:x)cout<<u.first<<" "<<u.second<<endl;
// cout<<endl;
ll a=0,b=x.size()-1;
ll out=-1;
while(a<=b)
{
ll m=(a+b)/2;
pair<ll,ll>p=*x.find_by_order(m);
if(p.first>round((e-s+1)/3.00))
{
out=p.second;
b=m-1;
}
else
{
a=m+1;
}
}
ans[j]=out;
}
for(int i=0;i<q;i++)cout<<ans[i]<<endl;
}