T162T3

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c))x=x*10+c-'0',gc;x*=k;
}

const int N=5e5+7;
const int S=710;

int a[N];
int be[N];
int val[N];
int Ans[N];
int L[S];
int R[S];
int lst[N];
int pre[N];
int nex[N];
int sum[N];
int ID[N];
int LG[N];
int st[N][20];

struct Query{
    int l,r,id;
    inline bool operator < (const Query &a)const{
        return be[l]==be[a.l]?r<a.r:l<a.l;
    }
}Q[N];

int n,q,tot;
int ans;

inline int solve(int l,int r){
    int ret=0;
    for(int i=l;i<=r;++i){
        if(pre[i]>=l){
            sum[ID[i]]+=i-pre[i];
            ret=max(ret,sum[ID[i]]);
        }
    }
    for(int i=l;i<=r;++i)sum[ID[i]]=0;
    return ret+1;
}

inline void Get(int x,int &i){
    int l=R[x]+1,r=R[x];
    memset(sum+1,0,tot<<2);
    for(ans=0;be[Q[i].l]==x;++i){
        if(be[Q[i].r]==x)continue;
        while(r<Q[i].r){
            r++;
            if(pre[r]>R[x]){
                sum[ID[r]]+=r-pre[r];
                ans=max(ans,sum[ID[r]]);
            }
        }
        ll t=ans;
        while(l>Q[i].l){
            l--;
            if(nex[l]<=r){
                sum[ID[l]]+=nex[l]-l;
                ans=max(ans,sum[ID[l]]);
            }
        }
        Ans[Q[i].id]=ans+1;
        while(l<R[x]+1){
            if(nex[l]<=r){
                sum[ID[l]]-=nex[l]-l;
            }
            l++;
        }
        ans=t;
    }
}

inline int query(int l,int r){
    int x=LG[r-l+1];
    return max(st[l][x],st[r-(1<<x)+1][x]);
}

int main(){
    freopen("spiral.in","r",stdin);
    freopen("spiral.out","w",stdout);
    r(n),r(q);
    const int SIZE=sqrt(n);
    for(int i=1;i<=n;++i){
        r(a[i]);
        be[i]=(i-1)/SIZE+1;
        if(!L[be[i]])L[be[i]]=i;
        R[be[i]]=i;
        val[i]=a[i];
    }
    sort(val+1,val+n+1);
    for(int i=1;i<=n;++i){
        a[i]=lower_bound(val+1,val+n+1,a[i])-val;
    }
    for(int i=2;i<=n;++i)LG[i]=LG[i>>1]+1;
    for(int i=1;i<=n;++i)st[i][0]=a[i];
    for(int j=1;j<=LG[n];++j){
        for(int i=1;i+(1<<j)-1<=n;++i){
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
        }
    }
    for(int i=1;i<=n;++i){
        pre[i]=0;
        nex[i]=n+1;
        if(lst[a[i]]&&query(lst[a[i]],i)==a[i]){
            pre[i]=lst[a[i]];
            nex[pre[i]]=i;
        }
        lst[a[i]]=i;
    }
    for(int i=1;i<=n;++i){
        if(!pre[i])ID[i]=++tot;
        else ID[i]=ID[pre[i]];
    }
    for(int i=1;i<=q;++i){
        r(Q[i].l),r(Q[i].r);
        if(be[Q[i].l]==be[Q[i].r]){
            Ans[i]=solve(Q[i].l,Q[i].r);
        }
        else Q[i].id=i;
    }
    sort(Q+1,Q+q+1);
    for(int i=1,x=1;i<=q;++x){
        Get(x,i);
    }
    for(int i=1;i<=q;++i){
        printf("%d\n",Ans[i]);
    }
}