tioj 2122

using namespace std;
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#define pb push_back
#include <utility>
#define pii pair<int,int>

struct Qs{
    int id;
    int st,ed;
};

int A[100100];
int appearCnt[100100],numCnt[100100];

void Init(){
    for (int i=0;i<100050;++i){
        appearCnt[i] = 0;
        numCnt[i] = 0;
    }
    appearCnt[1] = 1;
}

int main(){
    ios_base::sync_with_stdio(false),cin.tie(0);
    int n,q;

    cin >> n >> q;
    for (int i=1;i<=n;++i){
        cin >> A[i];
    }

    int const spaces = sqrt(n);
    vector <Qs> group[500]{};
    vector <pii> ans;

    for (int i=1;i<=q;++i){
        int s,e;

        cin >> s >> e;
        group[(s-1) / (n / spaces)].pb({i,s,e});
    }
    for (int i=0;i<=n/spaces;++i)
        sort (group[i].begin(),group[i].end(),[](Qs a,Qs b){return a.ed < b.ed;});

    for (int i=0;i<=spaces;++i){
        int LB = i * spaces + 1,RB = LB;
        int maxAppear = A[LB];
        Init();
        numCnt[A[LB]] = 1;

        for (auto d:group[i]){
            while (RB < d.ed){
                ++RB;
                --appearCnt[numCnt[A[RB]]];
                ++numCnt[A[RB]];
                ++appearCnt[numCnt[A[RB]]];
                if (numCnt[A[RB]] > numCnt[maxAppear]){
                    maxAppear = A[RB];
                }
            }
            while (LB > d.st){
                --LB;
                --appearCnt[numCnt[A[LB]]];
                ++numCnt[A[LB]];
                ++appearCnt[numCnt[A[LB]]];
                if (numCnt[A[LB]] > numCnt[maxAppear]){
                    maxAppear = A[LB];
                }
            }
            while (LB < d.st){
                --appearCnt[numCnt[A[LB]]];
                --numCnt[A[LB]];
                ++appearCnt[numCnt[A[LB]]];
                ++LB;
                if (!numCnt[maxAppear]){
                    maxAppear = A[LB];
                }
            }

            ans.pb({d.id,numCnt[maxAppear]});
        }
    }

    sort (ans.begin(),ans.end(),[](pii a,pii b){return a.first < b.first;});
    for (auto i:ans){
        cout << i.second << '\n';
    }

    return 0;
}