附代码：
#include <cstdio>
#include <algorithm>
using namespace std;
const int NMax=100100;
int N,M,L;
struct node {
	int l,r;
	pair<int,int> time,timel,timer;
	node *left,*right;
}*Tree,pool[NMax*2];
void Build(int x,int y,node *p) {
	p->l=x;p->r=y;p->left=p->right=NULL;p->timel=p->timer=p->time=make_pair(-1,-1);
	if(x<y) {
		int mid=(x+y)>>1;
		p->left=&pool[L++];p->right=&pool[L++];
		Build(x,mid,p->left);Build(mid+1,y,p->right);
	}
}
void Set(int a,int b,node *p) {
	if(p->l==p->r) {
		p->time=make_pair(b,1);p->timel=make_pair(b,1);p->timer=make_pair(b,1);
		return ;
	}
	int mid=(p->l+p->r)/2;
	if(a<=mid) Set(a,b,p->left);
	else Set(a,b,p->right);
	if(p->left->time.second>p->time.second) p->time=p->left->time;
	if(p->right->time.second>p->time.second) p->time=p->right->time;
	if(p->left->timer.first==p->right->timel.first&&p->left->timer.second+p->right->timel.second>p->time.second) {
		p->time.first=p->left->timer.first;
		p->time.second=p->left->timer.second+p->right->timel.second;
	}
	p->timel=p->left->timel;p->timer=p->right->timer;
	if(p->left->timel.first==p->left->timer.first&&p->left->timer.first==p->right->timel.first) {
		p->timel.first=p->left->timel.first;
		p->timel.second=p->left->timel.second+p->right->timel.second;
	}
	if(p->right->timer.first==p->right->timel.first&&p->right->timel.first==p->left->timer.first) {
		p->timer.first=p->right->timer.first;
		p->timer.second=p->right->timer.second+p->left->timer.second;
	}
}
pair<int,int> calc(int x,int y,node *p) {
	if(p->l==x&&p->r==y) return p->time;
	int mid=(p->l+p->r)/2;
	if(mid>=y) return calc(x,y,p->left);
	else if(mid<x) return calc(x,y,p->right);
	else {
		pair<int,int> ret1=calc(x,mid,p->left),ret2=calc(mid+1,y,p->right),ret=make_pair(-1,-1);
		if(ret1.first==ret2.first&&ret1.second+ret2.second>ret.second) ret=make_pair(ret1.first,ret1.second+ret2.second);
		pair<int,int> rightl=p->right->timel,leftr=p->left->timer;
		if(rightl.first==leftr.first) {
			//puts("Here");
			if(mid+rightl.second>y) rightl.second=y-mid;
			if(mid-leftr.second+1<x) leftr.second=mid-x+1;
			if(rightl.second+leftr.second>ret.second) ret=make_pair(rightl.first,rightl.second+leftr.second);
		}
		if(ret1.second>ret.second) ret=ret1;
		if(ret2.second>ret.second) ret=ret2;
		return ret;
	}
}
int main()
{
	int x,y;
	while(scanf("%d",&N),N) {
		L=0;
		scanf("%d",&M);
		Tree=&pool[L++];Build(1,N,Tree);
		for(int i=1;i<=N;i++) {
			scanf("%d",&x);
			Set(i,x,Tree);
		}
		for(int i=1;i<=M;i++) {
			scanf("%d%d",&x,&y);
			printf("%d\n",calc(x,y,Tree).second);
		}
	}
	getchar();getchar();
	return 0;
}