#include<bits/stdc++.h>
using namespace std;
const int NR=5e5+10;
const int INF=1e9;
int n,m,tot,a[NR],lg[NR],ans[NR],pre[NR],nxt[NR],buc[NR];
struct interval{
	int maxv,l,r;
	interval operator +(const interval &T)const{
		interval res;res.maxv=max(maxv,T.maxv);
		res.l=min((res.maxv==maxv)?l:INF,(res.maxv==T.maxv)?T.l:INF);
		res.r=max((res.maxv==maxv)?r:0,(res.maxv==T.maxv)?T.r:0);
		return res;
	}
}f[NR][20];
struct task{
	int l,r,id;
	bool operator <(const task &T)const{
		if(r!=T.r)return r<T.r;
		if(l!=T.l)return l>T.l;
		return id<T.id;
	}
}t[NR<<2];

void init(){
	for(int i=1;i<=n;i++)
		f[i][0]=interval{a[i],i,i},lg[i]=lg[i>>1]+1;
	for(int i=1;i<=19;i++)
		for(int j=1;j+(1<<i)<=n+1;j++)
			f[j][i]=f[j][i-1]+f[j+(1<<(i-1))][i-1];
}
interval query(int l,int r){
	int k=lg[r-l+1]-1;
	return f[l][k]+f[r-(1<<k)+1][k];
}

int c[NR];
int lowbit(int x){
	return x&(-x);
}
void modify(int x,int y){
	while(x<=n){
		c[x]=max(c[x],y);
		x+=lowbit(x);
	}
}
int ask(int x){
	int res=0;
	while(x){
		res=max(res,c[x]);
		x-=lowbit(x);
	}
	return res;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	init();
	for(int i=1;i<=n;i++){
		if(buc[a[i]]&&query(buc[a[i]],i).maxv==a[i]){
			pre[i]=buc[a[i]];
			while(pre[i]!=pre[pre[i]])pre[i]=pre[pre[i]];
		}
		else pre[i]=i;
		buc[a[i]]=i;
	}
	memset(buc,0,sizeof(buc));
	for(int i=n;i>=1;i--){
		if(buc[a[i]]&&query(i,buc[a[i]]).maxv==a[i]){
			nxt[i]=buc[a[i]];
			while(nxt[i]!=nxt[nxt[i]])nxt[i]=nxt[nxt[i]];
		}
		else nxt[i]=i;
		buc[a[i]]=i;
	}
	for(int i=1;i<=m;i++)cin>>t[i].l>>t[i].r,t[i].id=i;
	tot=m;
	for(int i=1;i<=n;i++){
		if(pre[i]!=i)t[++tot]=task{pre[i],i,0};
		if(nxt[i]!=i)t[++tot]=task{i,nxt[i],0};
	}
	sort(t+1,t+1+tot);
	for(int i=1;i<=tot;i++)
		if(t[i].id){
			auto tmp=query(t[i].l,t[i].r);
			ans[t[i].id]=max(tmp.r-tmp.l,ask(n+1-t[i].l));
		}
		else modify(n+1-t[i].l,t[i].r-t[i].l);
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
	return 0;
}