#include <bits/stdc++.h>
static char buf[1000000],*paa=buf,*pd=buf;
static char buf2[1000000],*pp=buf2;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline void pc(char ch){
    if(pp-buf2==1000000) fwrite(buf2,1,1000000,stdout),pp=buf2;
    *pp++=ch;
}
inline void pcc(){
    fwrite(buf2,1,pp-buf2,stdout);
    pp=buf2;
}
inline int read(void){
    register int x(0);register char c(getchar());
    while(c<'0'||c>'9'){c=getchar();}
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}
void write(int x){
    static int sta[20];
    int top=0;
    do{
        sta[top++]=x%10,x/=10;
    }while(x);
    while(top) pc(sta[--top]+48);
}
void we(int x){
    write(x);
    pc('\n');
}
int N,Q,a[500009],as[500009],v[500009];
std::vector<int> t[500009];
struct n_t{
    int l,r,i;
} q[500009];
bool operator<(n_t x,n_t y) {
    if(x.l!=y.l) return x.l<y.l;
    if(x.r==y.r) return x.i<y.i;
    return x.r>y.r;    
}
struct p_t{
    int a,b;
};
bool operator<(p_t x,p_t y) {
    return x.a<y.a;    
}
std::set<n_t> ss;
std::set<p_t> ss2;
void rm(int p);
#define ls (n<<1)
#define rs ((n<<1)|1)
#define md ((l+r)>>1)
int laz[2000009],ma[2000009];
void up(int n,int l,int r,int L,int R) {
    if(r<L||R<l) return;
    if(L<=l&&r<=R) {
        laz[n]++;
        ma[n]--;
        return;
    }
    up(ls,l,md,L,R);
    up(rs,md+1,r,L,R);
    ma[n]=std::max(ma[ls],ma[rs])-laz[n];
}
void cl(int n,int l,int r,int v) {
    if(l==r) {
        as[q[l].i]=v;
        rm(l);
        return;
    }
    ma[ls]-=laz[n];
    ma[rs]-=laz[n];
    laz[ls]+=laz[n];
    laz[rs]+=laz[n];
    laz[n]=0;
    if(ma[ls]>=v) {
        cl(ls,l,md,v);
    } else {
        cl(rs,md+1,r,v);
    }
}
void up2(int n,int l,int r,int p,int v) {
    if(l==r) {
        ma[n]=v;
        return;
    }
    ma[ls]-=laz[n];
    ma[rs]-=laz[n];
    laz[ls]+=laz[n];
    laz[rs]+=laz[n];
    laz[n]=0;
    if(p<=md) up2(ls,l,md,p,v);
    else up2(rs,md+1,r,p,v);
    ma[n]=std::max(ma[ls],ma[rs])-laz[n];
}
void er4(int n,int l,int r,int p) {
    if(l==r) {
        ma[n]=-0x3f3f3f3f;
        return;
    }
    ma[ls]-=laz[n];
    ma[rs]-=laz[n];
    laz[ls]+=laz[n];
    laz[rs]+=laz[n];
    laz[n]=0;
    if(p<=md) er4(ls,l,md,p);
    else er4(rs,md+1,r,p);
    ma[n]=std::max(ma[ls],ma[rs])-laz[n];
}

int ma2[2000009];
void er3(int n,int l,int r,int p) {
    if(l==r) {
        ma2[n]=-0x3f3f3f3f;
        return;
    }
    if(p<=md) er3(ls,l,md,p);
    else er3(rs,md+1,r,p);
    ma2[n]=std::max(ma2[ls],ma2[rs]);
}
void bd(int n,int l,int r) {
    if(l==r) {
        ma2[n]=q[l].r;
        return;
    }
    bd(ls,l,md);
    bd(rs,md+1,r);
    ma2[n]=std::max(ma2[ls],ma2[rs]);
}
int f2(int n,int l,int r,int v) {
    if(ma2[n]<v) return r+1;
    if(l==r) return l;
    int a=f2(ls,l,md,v);
    if(a==md+1) a=f2(rs,md+1,r,v);
    return a;
}


void is(int p) {
  //  printf("is %d\n",p);
    int l=q[p].l,r=q[p].r;
    ss.insert((n_t){l,r,p});
    ss2.insert((p_t){r,p});
    int va=r-l+1;
    for(int i=l;i<=r;i++) if(v[i]) va--;
    up2(1,1,Q,p,va);
    er3(1,1,Q,p);
}
void rm(int p) {
   // printf("rm %d\n",p);
    er4(1,1,Q,p);
    int l=q[p].l,r=q[p].r;
    ss2.erase((p_t){r,p});
    auto it=ss.find((n_t){l,r,p});
    int id=0;
    if(it==ss.begin()) {
        id=0;
    } else {
        it--;
        id=(*it).r;
    }
    //printf("%d\n",id);
    ss.erase((n_t){l,r,p});
    while(1) {
        int pt=f2(1,1,Q,id+1);
        if(pt>Q||q[pt].r>r) {
            break;
        }
        is(pt);
        id=q[pt].r;
    }
}
signed main(void) {
    N=read();Q=read();
    for(int i=1;i<=N;i++) {
        a[i]=read();
        t[a[i]].push_back(i);
    }
    for(int i=1;i<=Q;i++) {
        q[i].l=read();
        q[i].r=read();
        q[i].i=i;
    }
    std::sort(q+1,q+Q+1);
    int maa=0;
    memset(ma,-0x3f,sizeof(ma));
    bd(1,1,Q);
    for(int i=1;i<=Q;i++) {
        if(maa<q[i].r) {
            is(i);
            maa=q[i].r;
        }
    }
    for(int i=500000;i>=1;i--) {
        for(int j=0;j<t[i].size();j++) {
            int p=t[i][j];
            v[p]=1;
            int l=0,r=Q,mm;
            while(l<r) {
                mm=(l+r+1)/2;
                if(q[mm].l<=p) l=mm;else r=mm-1;
            }
            auto it=ss2.lower_bound((p_t){p,0});
            int tq;
            if(it==ss2.end()) {
                tq=Q+1;
            } else {
                tq=(*it).b;
            }
            if(tq<=l) {
             //   printf("%d %d %d\n",p,tq,l);
                up(1,1,Q,tq,l);
            }
        }
        while(ma[1]>=i) {
            cl(1,1,Q,i);
        }
    }
    for(int i=1;i<=Q;i++) we(as[i]);
    pcc();
}