#include<bits/stdc++.h>
//#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int buf[105];
inline void print(int x,char ch=' '){
	if(x<0) putchar('-'),x=-x;
	int tot=0;
	do{
		buf[++tot]=x%10;
		x/=10;
	}while(x);
	for(int i=tot;i;i--) putchar(buf[i]+'0');
	putchar(ch);
}
const int MAXN=5e5+5;
int n,m,B,a[MAXN],b[MAXN];

int st[MAXN][20],lg[MAXN];
int query(int l,int r){
	int b=lg[r-l+1];
	return max(st[l][b],st[r-(1<<b)+1][b]);
}

int premx[MAXN],sufmx[MAXN];
int mp[MAXN];
void init(){
	for(int i=1;i<=n;i++){
		if(mp[a[i]])
			premx[i]=query(mp[a[i]],i);
		mp[a[i]]=i;
	}
	memset(mp,0,sizeof(mp));
	for(int i=n;i;i--){
		if(mp[a[i]])
			sufmx[i]=query(i,mp[a[i]]);
		else mp[a[i]]=i;
	}
}

int ans[MAXN];
int f[MAXN],g[MAXN];
struct node{
	int l,r,id;
	node(int a=0,int b=0,int c=0){
		l=a,r=b,id=c;
	}
	bool friend operator<(const node &a,const node &b){
		return a.r<b.r;
	}
};
vector<node> qry[MAXN];

#define pr(x,y) make_pair(x,y)
#define F first
#define S second
pair<int,int> pre[MAXN],suf[MAXN];
pair<int,int> tmp1[MAXN],tmp2[MAXN];
void solve(int mid){
	sort(qry[mid].begin(),qry[mid].end());
	
	int pos=mid,mx=0;
	for(auto q:qry[mid]){
		while(pos<=q.r){
			if(suf[a[pos]].S&&premx[pos]<=a[pos]){
				if(pre[a[pos]]==suf[a[pos]])
					pre[a[pos]].S=suf[a[pos]].S=pos;
				else
					suf[a[pos]].S=pos;
			}
			else{
				suf[a[pos]]=pr(pos,pos);
				if(!pre[a[pos]].F) pre[a[pos]]=pr(pos,pos);
			}
			mx=max(mx,suf[a[pos]].S-suf[a[pos]].F);
			pos++;
		}
		
		int cpy=mx;
		for(int i=mid-1;i>=q.l;i--)
			tmp1[a[i]]=pre[a[i]],tmp2[a[i]]=suf[a[i]];
		
		for(int i=mid-1;i>=q.l;i--){
			if(pre[a[i]].F&&sufmx[i]<=a[i]){
				if(pre[a[i]]==suf[a[i]])
					pre[a[i]].F=suf[a[i]].F=i;
				else
					pre[a[i]].F=i;
			}
			else{
				pre[a[i]]=pr(i,i);
				if(!suf[a[i]].F) suf[a[i]]=pr(i,i);
			}
			mx=max(mx,pre[a[i]].S-pre[a[i]].F);
		}
		ans[q.id]=mx;
		
		mx=cpy;
		for(int i=mid-1;i>=q.l;i--)
			pre[a[i]]=tmp1[a[i]],suf[a[i]]=tmp2[a[i]];
	}
	
	for(int i=1;i<=n;i++) pre[a[i]]=suf[a[i]]=pr(0,0);
}
mt19937 rd(time(0));
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=b[i]=read();
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+n+1,a[i])-b;
	
	for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<=n;i++) st[i][0]=a[i];
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
	init();
	
	B=sqrt(n);
	B+=rd()%B+1;
	for(int i=1;i<=m;i++){
		int l=read(),r=read();
		if(r-l+1<=B){
			for(int j=l;j<=r;j++){
				if(f[a[j]]&&premx[j]<=a[j])
					g[a[j]]+=j-f[a[j]];
				else g[a[j]]=0;
				f[a[j]]=j;
				ans[i]=max(ans[i],g[a[j]]);
			}
			for(int j=l;j<=r;j++)
				f[a[j]]=g[a[j]]=0;
		}
		else{
			if((l-1)%B==0) qry[l].push_back(node(l,r,i));
			else{
				int id=((l-1)/B+1)*B+1;
				qry[id].push_back(node(l,r,i));
			}
		}
	}
	
	for(int i=1;i<=n;i+=B)
		solve(i);
	
	for(int i=1;i<=m;i++) print(ans[i],'\n');
	return 0;
}