Frequent values

Description

You are given a sequence of n integers a1 , a2 , ... , an 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 ai , ... , aj.

Input

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 a1 , ... , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: ai ≤ ai+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

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 102 31 105 100`

Sample Output

```143题意：查找区间内数出现最多的次数
#include <stdio.h>#include <stdlib.h>#include <math.h>#define maxn 100010#define Max(a, b) a > b ? a : bint num[maxn], v[maxn], rq[maxn];void build(int n){    int i, j, m, r = n, c = log((double)n) / log(2.0);    for (i = 1; i <= n; i++)    {        rq[i] = v[i];    }    for (i = 1; i <= c; i++)    {        for (j = 1; j <= r; j++)        {            m = j + (1 << (i - 1));a            if (m <= r)            {                rq[j][i] = Max(rq[j][i-1], rq[m][i-1]);            }            else            {                rq[j][i] = rq[j][i-1];            }        }    }}int rmq(int l, int r){    int len = r - l + 1;    int k = log(double(len)) / log(2.0);    int m = r - (1 << k) + 1;    return Max(rq[l][k], rq[m][k]);}int query(int l, int r){    int left, i;    if (num[l] == num[r])    {        return r - l + 1;    }    for (i = l; ; i++)    {        if (v[i] == 1)        {            left = i - l;            break;        }    }    return Max(left, rmq(i, r));}int main(){    int n, m, i, l, r;    while (scanf("%d%d", &n, &m) == 2)    {        scanf("%d", &num);        v = 1;        for (i = 2; i <= n; i++)        {            scanf("%d", &num[i]);            if (num[i] == num[i-1])            {                v[i] = v[i-1] + 1;            }            else            {                v[i] = 1;            }        }        build(n);        while (m--)        {            scanf("%d%d", &l, &r);            printf("%d\n", query(l, r));        }    }    return 0;}
```