/*
    题意：给出一个递增序列，给出询问区间，问出现次数最多是多少
    查询次数最大，可以用RMQ
    先离散化得到
    index[x[i]] 数x[i]是离散化后是第几
    start[j] 第j个第一次在x[]出现的位置
    f[] 表示出现次数
    然后对于查询区间，分3种情况讨论一下！！
*/    
#include<cstdio>
#include<cstring>
#include<cmath>

inline int max(int a,int b){return a>b?a:b;}

const int MAXN = 100005;

int rmq[MAXN][20],x[MAXN],f[MAXN];
int index[2*MAXN],start[MAXN];
int N,Q,NN;

void initRMQ()
{
    for(int i=1;i<=N;i++)rmq[i][0]=i;
    for(int j=1;(1<<j)<=N;j++)
        for(int i=1;i+(1<<j)-1<=N;i++)
            if(f[rmq[i][j-1]]>f[rmq[i+(1<<(j-1))][j-1]])rmq[i][j]=rmq[i][j-1];
            else rmq[i][j]=rmq[i+(1<<(j-1))][j-1];
}

int query(int L,int R)
{
    int iL = index[x[L]] , iR = index[x[R]];
    int sL = start[iL],sR = start[iR];
    if(iL==iR)return R-L+1;
    else if(iL==iR-1)return max(sR-L,R-sR+1);
    else
    {
        int ans = max(start[iL+1]-L,R-sR+1);
        int a = iL+1,b =iR-1 ;
        int k = log(1.0+b-a)/log(2.0);
        ans = max(ans,max(f[rmq[a][k]],f[rmq[b-(1<<k)+1][k]]));
        return ans;
    }
}

int main()
{
    int L,R;
    while(scanf("%d",&NN),NN)
    {
        memset(f,0,sizeof(f));
        scanf("%d",&Q);
        N = x[0] = 0;
        for(int i=1;i<=NN;i++)
        {
            scanf("%d",&x[i]);
            x[i]+=MAXN;
            if(x[i]!=x[i-1])
            {
                index[x[i]] = ++N;
                start[N] = i;
            }
            f[N]++;
        }
        initRMQ();
        while(Q--)
        {
            scanf("%d%d",&L,&R);
            printf("%d\n",query(L,R));
        }
    }
    return 0;
}