/*

线段树区间合并

维护几个信息 到时候乱搞一下就好了

开始T了 有一种情况可以不用递归 直接算出来

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 100010

#define lc (k<<1)

#define rc (k<<1)+1

#define mid ((l+r)>>1)

using namespace std;

int n,m,a[maxn],ls[maxn*],rs[maxn*],ln[maxn*],rn[maxn*],s[maxn*];

int init(){

    int x=,f=;char s=getchar();

    while(s<''||s>''){if(s=='-')f=-;s=getchar();}

    while(s>=''&&s<=''){x=x*+s-'';s=getchar();}

    return x*f;

}

void Build(int k,int l,int r){

    if(l!=r){

        Build(lc,l,mid);

        Build(rc,mid+,r);

        s[k]=max(s[lc],s[rc]);

        if(rn[lc]==ln[rc])

            s[k]=max(s[k],rs[lc]+ls[rc]);

        ln[k]=ln[lc];rn[k]=rn[rc];

        ls[k]=ls[lc];rs[k]=rs[rc];

        if(ls[lc]==mid-l+&&rn[lc]==ln[rc])

            ls[k]=max(ls[k],ls[lc]+ls[rc]);

        if(rs[rc]==r-mid&&rn[lc]==ln[rc])

            rs[k]=max(rs[k],rs[rc]+rs[lc]);

    }

    else{

        ls[k]=rs[k]=;ln[k]=rn[k]=a[l];s[k]=;

    }

}

int Query(int k,int l,int r,int x,int y){

    if(x<=l&&y>=r)return s[k];

    int ret=,L,R;

    if(y<=mid)return Query(lc,l,mid,x,y);

    else if(x>mid)return Query(rc,mid+,r,x,y);

    else{

        if(rn[lc]==ln[rc]){

            L=max(mid-rs[lc]+,x);

            R=min(mid+ls[rc],y);

            ret=mid-L++R-mid;

        }

            //ret=Query(lc,l,mid,max(mid-rs[lc]+1,x),mid)

            //+Query(rc,mid+1,r,mid+1,min(mid+ls[rc],y));可以只结算出来 QAQ T了好几遍

        ret=max(ret,Query(lc,l,mid,x,y));

        ret=max(ret,Query(rc,mid+,r,x,y));

    }

    return ret;

}

int main()

{

    while(){

        n=init();if(n==)break;

        m=init();

        for(int i=;i<=n;i++)a[i]=init();

        Build(,,n);

        while(m--){

            int L,R;

            L=init();R=init();

            printf("%d\n",Query(,,n,L,R));

        }

    }

    return ;

}

/*

ST表做法 比较巧妙 时间差不多 空间大一些

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 100010

using namespace std;

int n,m,a[maxn],c[maxn],f[maxn][],lst[maxn],p[maxn];

int init(){

    int x=,f=;char s=getchar();

    while(s<''||s>''){if(s=='-')f=-;s=getchar();}

    while(s>=''&&s<=''){x=x*+s-'';s=getchar();}

    return x*f;

}

void Clear(){

    memset(c,,sizeof(c));

    memset(f,,sizeof(f));

    memset(lst,,sizeof(lst));

}

void Get_p(){

    for(int i=;i<=maxn-;i++)

        for(int j=;j<=;j++)

            if((<<j)>i){

                p[i]=j-;break;

            }

}

void Get_ST(){

    for(int i=;i<=n;i++)f[i][]=c[i];

    for(int j=;j<=;j++)

        for(int i=;i+(<<j)-<=n;i++)

            f[i][j]=max(f[i][j-],f[i+(<<j-)][j-]);

}

int Query(int l,int r){

    if(l>r)return ;

    int k=p[r-l+];

    return max(f[l][k],f[r-(<<k)+][k]);

}

int main()

{

    Get_p();

    while(){

        n=init();if(n==)break;m=init();

        Clear();

        for(int i=;i<=n;i++)a[i]=init();

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

            if(a[i]==a[i-])c[i]=c[i-]+;

            else c[i]++;

        for(int i=n;i>=;i--)

            if(a[i]==a[i+])lst[i]=lst[i+];

            else lst[i]=i;

        Get_ST();

        while(m--){

            int L,R,mxx=,mx=;

            L=init();R=init();

            mxx=Query(lst[L]+,R);

            mx=min(lst[L],R)-L+;

            printf("%d\n",max(mxx,mx));

        }

    }

    return ;

}