话说现在POJ的机器是不是有点卡啊  提交之后经常有7,8份代码在waiting

#include<cstdio>
#include<iomanip>
#include<iostream>
#include<algorithm>
using namespace std;

#define maxn 100010

int n, m;
int input[maxn], start[maxn << 1], End[maxn << 1];

struct Node {
	int l, r, lval, rval, mval, mfru;
}cover[maxn << 2];

struct Point {
	int val, fru;
};

Point eg;

void pushup(int rt)
{
	cover[rt].lval = cover[rt << 1].lval;
	cover[rt].rval = cover[rt << 1 | 1].rval;
	cover[rt].mfru = max(cover[rt << 1].mfru, cover[rt << 1 | 1].mfru);
	cover[rt].mval = cover[rt << 1].mfru > cover[rt << 1 | 1].mfru ? cover[rt << 1].mval : cover[rt << 1 | 1].mval;
	if (cover[rt << 1].rval == cover[rt << 1 | 1].lval)
	{
		int l = max(cover[rt].l, start[cover[rt << 1].rval + 100010]);
		int r = min(cover[rt].r, End[cover[rt << 1 | 1].lval + 100010]);
		if (r - l + 1 > cover[rt].mfru)
		{
			cover[rt].mfru = r - l + 1;
			cover[rt].mval = cover[rt << 1].rval;
		}
	}
}

void build(int rt, int l, int r)
{
	cover[rt].l = l;
	cover[rt].r = r;
	if (l == r)
	{
		cover[rt].mfru = 1;
		cover[rt].mval = cover[rt].lval = cover[rt].rval = input[l];
		return;
	}
	int m = (l + r) >> 1;
	build(rt << 1, l, m);
	build(rt << 1 | 1, m + 1, r);
	pushup(rt);
}

Point query(int rt, int qstart, int qend)
{
	if (qstart <= cover[rt].l&&cover[rt].r <= qend)
	{
		eg.val = cover[rt].mval;
		eg.fru = cover[rt].mfru;
		return eg;
	}
	int m = (cover[rt].l + cover[rt].r) >> 1;
	if (m >= qend)
		return query(rt << 1, qstart, qend);
	if (m < qstart)
		return query(rt << 1 | 1, qstart, qend);
	Point p1 = query(rt << 1, qstart, qend), p2 = query(rt << 1 | 1, qstart, qend);
	Point tmp = p1.fru > p2.fru ? p1 : p2;
	if (cover[rt << 1].rval != cover[rt << 1 | 1].lval)
		return tmp;
	int l = max(max(qstart, start[cover[rt << 1].rval + 100010]), cover[rt << 1].l);
	int r = min(min(qend, End[cover[rt << 1 | 1].lval + 100010]), cover[rt << 1 | 1].r);
	if (r - l + 1 <= tmp.fru) return tmp;
	tmp.val = cover[rt << 1].rval;
	tmp.fru = r - l + 1;
	return tmp;
}

int main()
{

	ios::sync_with_stdio(false);

	while (cin >> n&&n)
	{
		scanf("%d", &m);
		//cin >> m;
		memset(start, 0, sizeof(start));
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &input[i]);
			//cin >> input[i];
			if (!start[input[i] + 100010]) start[input[i] + 100010] = i;
			End[input[i] + 100010] = i;
		}
		build(1, 1, n);
		int l, r;
		for (int i = 1; i <= m; i++)
		{
			scanf("%d%d", &l, &r);
			//cin >> l >> r;
			printf("%d\n", query(1, l, r).fru);
			//cout << query(1, l, r).fru << endl;
		}
	}
	return 0;
}