#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=sqrt(300010);
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();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;
}