离散化+RMQ问题。首先读入序列A，把序列中元素离散化到B，存储值相同的元素的个数，以及每个值第一次在A中出现的位置Start[i]。然后对序列B进行SparseTable预处理(ST算法)。对于每个询问，求[x,y]之间最频繁出现的值的个数，算出x,y对应的序列B中位置a,b。然后根据a,b大小的不同，分三种情况考虑。

• 若a与b相等，则询问的区间[x,y]值全部相同，结果就是y-x+1。
• 若a+1=b，则[x,y]恰好跨两个值的区间，结果就是两个值的个数的较大值Max(Start[b]-x,y-Start[b]+1)。
• 若a+1<b，则[x,y]跨多个值，则最大值除了在两边意外，还可能会是B[a+1..b-1]中的最大值，用处理好的SparseTable求序列B中[a+1,b-1]的最大值即可。

/* 
 * Problem: pku3368 Frequent values
 * Author: Guo Jiabao
 * Time: 2009.4.1 19:30
 * State: Solved
 * Memo: RQM SparseTable
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
const int MAXN=100001,LG=18,INF=0x7FFFFFFF;
using namespace std;
int M,N,Q;
int A[MAXN],Map[MAXN],F[MAXN][LG],Start[MAXN],Log[MAXN];
void init()
{
    int i,k;
    freopen("frequent.in","r",stdin);
    freopen("frequent.out","w",stdout);
    A[N=0]=INF;
    for (i=1,k=0;i<MAXN;i++)
    {
        if (1<<(k+1)<=i)
            k++;
        Log[i]=k;
    }
}
bool readfile()
{
    scanf("%d",&M);
    if (M==0) return false;
    scanf("%d",&Q);
    for (int i=1;i<=M;i++)
    {
        scanf("%d",&A[i]);
        if (A[i]!=A[i-1])
        {
            Map[i]=++N;
            Start[N]=i;
            F[N][0]=1;
        }
        else
        {
            Map[i]=N;
            F[N][0]++;
        }
    }
    return true;
}
inline int Max(int a,int b){return a>b?a:b;}
void SpraseTable()
{
    int i,j,jt;
    for (j=jt=1;jt<=N;j++,jt=jt<<1)
    {
        for (i=1;i+jt<=N;i++)
        {
            F[i][j]=Max(F[i][j-1],F[i+jt][j-1]);
        }
    }
}
void Query()
{
    int i,ta,tb,a,b,k,tk,Ans;
    for (i=1;i<=Q;i++)
    {
        scanf("%d%d",&ta,&tb);
        a=Map[ta];b=Map[tb];
        if (a==b)
            Ans=tb-ta+1;
        else if (b==a+1)
            Ans=Max(Start[b]-ta,tb-Start[b]+1);
        else
        {
            Ans=Max(Start[a+1]-ta,tb-Start[b]+1);
            a++;b--;
            k=Log[b-a+1];
            tk=1<<k;
            Ans=Max(Ans,F[a][k]);
            Ans=Max(Ans,F[b-tk+1][k]);
        }
        printf("%dn",Ans);
    }
}
int main()
{
    init();
    while (readfile())
    {
        SpraseTable();
        Query();
    }
}