#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#include<cctype>

#include<cmath>

#define maxn 300000

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

int s[maxn];

int q[maxn];

int d[maxn];

int ans[maxn];

struct Que{

    int x,y,id;

    bool operator <(const Que a)const{

        if(s[x]!=s[a.x])    return s[x]<s[a.x];

        return y<a.y;

    }

}que[maxn];

int sum[maxn],cnt[maxn];

int main(){

    int n=read(),m=read();

    int sqt=sqrt(n);

    for(int i=;i<=n;++i){

        q[i]=d[i]=read();

        s[i]=(i-)/sqt+;

    }

    sort(q+,q+n+);

    int size=unique(q+,q+n+)-q-;

    for(int i=;i<=n;++i)    d[i]=lower_bound(q+,q+size+,d[i])-q;

    for(int i=;i<=m;++i)    que[i]=(Que){read(),read(),i};

    sort(que+,que+m+);

    int l=,r=,now=;cnt[]=;

    for(int i=;i<=m;++i){

        int x=que[i].x,y=que[i].y;

        while(r<y){

            r++;

            int &o=sum[d[r]];

            if(now==o)    now++;

            cnt[o]--;    o++;    cnt[o]++;

        }

        while(r>y){

            int &o=sum[d[r]];

            cnt[o]--;    if(now==o&&cnt[o]==)    now--;

            o--;    cnt[o]++;

            r--;

        }

        while(l<x){

            int &o=sum[d[l]];

            cnt[o]--;    if(now==o&&cnt[o]==)    now--;

            o--;    cnt[o]++;

            l++;

        }

        while(l>x){

            l--;

            int &o=sum[d[l]];

            cnt[o]--;    if(now==o)    now++;

            o++;    cnt[o]++;

        }

        ans[que[i].id]=now;

    }

    for(int i=;i<=n;++i)    printf("%d\n",-ans[i]);

    return ;

}