#include<bits/stdc++.h>
using namespace std;
namespace wxh666{
    //#define getchar getchar_unlocked
    //#define putchar putchar_unlocked
    #define sqrt(a) __builtin_sqrt(a)
    #define f(a,b,c) for(int a=b;a<=c;a++)
    #define ff(a,b,c) for(int a=b;a>=c;a--)
    #define g(n) f(i,1,n)
    #define df(n,m) g(n) f(j,1,m)
    #define max max_by_wxh
    template<typename T>
    inline T max_by_wxh(T x,T y) {return ((x)>(y)?(x):y);}
    template<typename T,typename ...Args>
    inline T max_by_wxh(T x,Args ...xs) {return max_by_wxh(x,max_by_wxh(xs...));}
    #define min min_by_wxh
    template<typename T>
    inline T min_by_wxh(T x,T y) {return ((x)<(y)?(x):y);}
    template<typename T,typename ...Args>
    inline T min_by_wxh(T x,Args ...xs) {return min_by_wxh(x,min_by_wxh(xs...));}
    template<typename T>
    inline void read(T &ans)
    {
        char ch=getchar();int f=1;ans=0;
        for(;!isdigit(ch);ch=getchar()) ch=='-'?f=-1:f=1;
        for(;isdigit(ch);ch=getchar()) ans=(ans<<3)+(ans<<1)+(ch&15);
        ans*=f;
        return;
    }
    template<typename T,typename ...Args>
    inline void read(T &tmp,Args &...tmps){read(tmp);read(tmps...);}
    inline int read()
    {
        char ch=getchar();int f=1,ans=0;
        for(;!isdigit(ch);ch=getchar()) ch=='-'?f=-1:f=1;
        for(;isdigit(ch);ch=getchar()) ans=(ans<<3)+(ans<<1)+(ch&15);
        return f*ans;
    }
    #define in read()
    template<typename T>
    inline void pu(T x)
    {
        ios::sync_with_stdio(false);
        cout<<x;
        ios::sync_with_stdio(true);
        return;
    }
    template<typename T>
    inline void pk(T x)
    {
        ios::sync_with_stdio(false);
        cout<<x<<" ";
        ios::sync_with_stdio(true);
        return;
    }
    inline void pk(char x)
    {
        ios::sync_with_stdio(false);
        cout<<x;
        if(x!='\n') cout<<' ';
        ios::sync_with_stdio(true);
        return;
    }
    template<typename T,typename ...Args>
    inline void pu(T x,Args ...xs){pu(x);pu(xs...);}
    template<typename T,typename ...Args>
    inline void ppu(T x,Args ...xs){pu(x,xs...,'\n');}
    template<typename T,typename ...Args>
    inline void pk(T x,Args ...xs){pk(x);pk(xs...);}
    template<typename T,typename ...Args>
    inline void ppk(T x,Args ...xs){pk(x,xs...,'\n');}
    #define cs(dt,n,m) \
    for(int i=1;i<=n;i++)\
    {\
        for(int j=1;j<=m;j++)\
            printf("%d ",dt[i][j]);\
        cout<<endl;\
    }
};using namespace wxh666;
template<size_t N=100005,bool Mode=1>
struct ST{
    int st[N+5][(int)(ceil(log2(N)))];
    void build(int* a,int n=N)
    {
        g(n) st[i][0]=a[i];
        f(j,1,ceil(log2(N))) f(i,1,n-(1<<j)+1)
            st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
        return;
    }
    int ask(int l,int r)
    {
        l+=100002;r+=100002;
        int k=log2(r-l+1);
        return max(st[l][k],st[r-(1<<k)+1][k]);
    }
};
ST<200005>st;
int n,q;
int a[100005];
int cnts[200005];
int l,r;
void check(int l,int r)
{
    if(r<l) {printf("0\n");return;}
    int lx=upper_bound(&a[l],&a[r+1],a[l])-&a[0]-1;
    int rx=lower_bound(&a[l],&a[r+1],a[r])-&a[0];
    if(a[l]==a[r]) printf("%d\n",r-l+1);else
    if(r==l+1) printf("1\n");else
    if(lx>=rx) printf("%d",r-l+1);else
    printf("%d\n",max(st.ask(a[lx]+1,a[rx]-1),lx-l+1,r-rx+1));
}
int main()
{
    while(cin>>n>>q)
    {
        if(n==0) return 0;
        g(n) a[i]=in,cnts[100002+a[i]]++;
        st.build(cnts);
        while(q--)
        {
            read(l,r);
            check(l,r);
        }
        // cerr<<st.ask(-1,10);
        memset(cnts,0,sizeof(cnts));
    }
    return 0;
}