You are given a sequence of n integers a₁ , a₂ , ... , a_n in non-decreasing order. In addition to that, you are given several queries consisting of indices
i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers
a_i , ... , a_j.

Input Specification

The input consists of several test cases. Each test case starts with a line containing two integers
n and q (1 ≤ n, q ≤ 100000). The next line contains
n integers a₁ , ... , a_n (-100000 ≤ a_i ≤ 100000, for each
i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: a_i ≤ a_i+1. The following
q lines contain one query each, consisting of two integers
i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the query.

The last test case is followed by a line containing a single 0.

Output Specification

For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.

Sample Input

10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0

Sample Output

1
4
3

题意和分析 大白书上很清晰 P198

// Accepted C++ 0.212  2014-08-27 02:42:35
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 200000
int count[MAXN];
int val[MAXN];
int l[MAXN];
int r[MAXN];
int num[MAXN];
int d[MAXN][35];
int sum;
void init_rmq()
{
    for(int i=1;i<=sum;i++) d[i][0]=count[i];
    for(int j=1;(1<<j)<=sum;j++)
    for(int i=1;i+(1<<j)<=sum;i++)
    d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}
int rmq(int a,int b)
{
    int k=0;
    while((1<<(k+1)) <= b-a+1) k++;
    return max(d[a][k],d[b-(1<<k)+1][k]);
}

int main()
{
    int n,q;
    while(~scanf("%d",&n)&&n)
    {
        scanf("%d",&q);
        int flag=-0x3f3f3f3f;
        sum=0;
        memset(count,0,sizeof(count));
        int t;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&t);
            if(flag==t)
            {
                count[sum]++;
                r[sum]++;
            }
            else
            {
                val[++sum]=t;
                count[sum]++;
                flag=t;
                l[sum]=i;
                r[sum]=i;
            }
            num[i]=sum;
        }
        init_rmq();
        while(q--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(num[a]==num[b]) printf("%d\n",b-a+1);
            else
            {
                int s1= r[num[a]] - a+1;
                int s2= b-l[num[b]]+1;
                int s3=0;
                if(num[a]+1<=num[b]-1)
                s3=rmq( num[a]+1 , num[b]-1 );
                printf("%d\n",max( max(s1,s2),s3 ));
            }

        }

    }
    return 0;
}
/**
7 100
-1 1 1 2 2 2 4
**/