#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=555;
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;
}
map<ll,ll>mp;
pbds x;
ll l,r;
ll curr_ans=-1;
void add(ll val)
{
    if(mp.find(val)!=mp.end())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]>0)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)
        {
            r--;
            remove(arr[r+1]);
        }
        while(s>l)
        {
            l++;
            remove(arr[l-1]);
        }
        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>(r-l+1)/3)
            {
                out=p.second;
                b=m-1;
            }
            else
            {
                a=m+1;
            }
        }
        ans[j]=out;
    }
    for(int i=0;i<q;i++)cout<<ans[i]<<endl;

}