Time Limit: 2000MS Memory Limit: 65536KB 64bit IO Format: %lld & %llu

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 andj (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 10
2 3
1 10
5 10
0

Sample Output

1
4
3

Source

AC代码：
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 10;
int a[maxn], f[maxn];
int dp[maxn][20], mm[maxn];
void initrmq(int n, int b[])
{
mm[0] = -1;
for (int i = 1; i <= n; i++)
{
mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];
dp[i][0] = b[i];
}
for (int j = 1; j <= mm[n]; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
int rmq(int x, int y)
{
int k = mm[y - x + 1];
return max(dp[x][k], dp[y - (1 << k) + 1][k]);
}
int main()
{
int n, q;
while (scanf("%d%d", &n, &q) == 2)
{
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int l, r;
f[1] = 1;
for (int i = 2; i <= n; i++)
f[i] = (a[i] == a[i - 1]) ? f[i - 1] + 1 : 1;
initrmq(n, f);
while (q--)
{
scanf("%d%d", &l, &r);
int tmp = 0, pos = l;
while (pos <= r && a[pos] == a[pos - 1])
pos++, tmp++;
printf("%d\n", max(tmp, rmq(pos, r)));
}
}
return 0;
}