#include<bits/stdc++.h>
using namespace std;
int n,q,a[500005];
struct apple{
	int l,r,wz;
	bool operator<(const apple &other)const{
		if(l==other.l)return r>other.r;
		return l<other.l;
	}
}e[500005];
int id[500005];
int ls[8000005],rs[8000005],tot=0;
int xz;
vector<int>gg[8500005];
int deg[8500005];
void addedge(int x,int y){
	gg[x].emplace_back(y);++deg[y];
}
void add(int x,int y,int l,int r,int z){
	if(l==r){
		if(x)addedge(y+q,x+q);
		addedge(y+q,xz);
		return;
	}
	int mid=(l+r)>>1;
	ls[y]=ls[x],rs[y]=rs[x];
	if(z<=mid)add(ls[x],ls[y]=++tot,l,mid,z);
	else add(rs[x],rs[y]=++tot,mid+1,r,z);
}
void query(int x,int l,int r,int ll,int rr){
	if(l>=ll&&r<=rr){
		addedge(xz,x+q);
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=ll&&ls[x])query(ls[x],l,mid,ll,rr);
	if(mid<rr&&rs[x])query(rs[x],mid+1,r,ll,rr);
}
#define M 500000
vector<int>g[500005];
int ans[500005];
int c[500005];
void addf(int x,int s){
	while(x<=n){
		c[x]+=s;
		x+=x&-x;
	}
}
int queryf(int x){
	int ans=0;
	while(x){
		ans+=c[x];
		x-=x&-x;
	}
	return ans;
}
int sm[1200005],s2[1200005],lz[1200005];
void pushdown(int o){
	if(!lz[o])return;
	sm[o<<1]+=lz[o],lz[o<<1]+=lz[o];
	sm[o<<1|1]+=lz[o],lz[o<<1|1]+=lz[o];
	lz[o]=0;
}
void build(int l,int r,int o){
	if(l==r){
		sm[o]=-1e9,s2[o]=l;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,o<<1);
	build(mid+1,r,o<<1|1);
	if(sm[o<<1]>sm[o<<1|1])sm[o]=sm[o<<1],s2[o]=s2[o<<1];
	else sm[o]=sm[o<<1|1],s2[o]=s2[o<<1|1];
}
void modify(int l,int r,int o,int x,int z){
	if(l==r){
		sm[o]=z;
		return;
	}
	pushdown(o);
	int mid=(l+r)>>1;
	if(x<=mid)modify(l,mid,o<<1,x,z);
	else modify(mid+1,r,o<<1|1,x,z);
	if(sm[o<<1]>sm[o<<1|1])sm[o]=sm[o<<1],s2[o]=s2[o<<1];
	else sm[o]=sm[o<<1|1],s2[o]=s2[o<<1|1];
}
void addd(int l,int r,int o,int ll,int rr,int s){
	if(l>=ll&&r<=rr){
		sm[o]+=s;lz[o]+=s;
		return;
	}
	pushdown(o);
	int mid=(l+r)>>1;
	if(mid>=ll)addd(l,mid,o<<1,ll,rr,s);
	if(mid<rr)addd(mid+1,r,o<<1|1,ll,rr,s);
	if(sm[o<<1]>sm[o<<1|1])sm[o]=sm[o<<1],s2[o]=s2[o<<1];
	else sm[o]=sm[o<<1|1],s2[o]=s2[o<<1|1];
}
set<pair<int,int>>se1,se2;
void jia(int z){
	int zz=queryf(e[z].r)-queryf(e[z].l-1);
	modify(1,q,1,z,zz);
	se1.emplace(e[z].l,z);
	se2.emplace(e[z].r,z);
}
queue<int>qu;
void jqq(int y){
	for(auto cu:gg[y]){
		--deg[cu];
		if(!deg[cu]){
			if(cu<=q){
				jia(cu);
			}else{
				qu.emplace(cu);
			}
		}
	}
	if(y>q&&ls[y-q]){
		int cu=ls[y-q]+q;
		--deg[cu];
		if(!deg[cu]){
			if(cu<=q){
				jia(cu);
			}else{
				qu.emplace(cu);
			}
		}
	}
	if(y>q&&rs[y-q]){
		int cu=rs[y-q]+q;
		--deg[cu];
		if(!deg[cu]){
			if(cu<=q){
				jia(cu);
			}else{
				qu.emplace(cu);
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		g[a[i]].emplace_back(i);
	}
	for(int i=1;i<=q;++i){
		scanf("%d%d",&e[i].l,&e[i].r);
		e[i].wz=i;
	}
	sort(e+1,e+q+1);
	for(int i=q;i>=1;--i){
		xz=i;
		add(id[i+1],id[i]=++tot,1,n,e[i].r);
		if(id[i+1])query(id[i+1],1,n,1,e[i].r);
	}
	for(int i=1;i<=tot;++i){
		if(ls[i])++deg[ls[i]+q];
		if(rs[i])++deg[rs[i]+q];
	}
	for(int i=1;i<=n;++i){
		addf(i,1);
	}
	build(1,q,1);
	for(int i=1;i<=tot+q;++i)if(!deg[i]){
		if(i<=q){
			jia(i);
		}else{
			qu.emplace(i);
		}
	}
	while(qu.size()){
		int y=qu.front();qu.pop();
		jqq(y);
	}
	for(int an=M;an>=0;--an){
		while(sm[1]>=an+1){
			int t=s2[1];
			se1.erase(make_pair(e[t].l,t));
			se2.erase(make_pair(e[t].r,t));
			ans[e[t].wz]=an+1;
			modify(1,q,1,t,-1e9);
			jqq(t);
			while(qu.size()){
				int y=qu.front();qu.pop();
				jqq(y);
			}
		}
		for(auto x:g[an]){
			addf(x,-1);
			auto t1=se2.lower_bound(make_pair(x,0));
			auto t2=se1.lower_bound(make_pair(x+1,0));
			if(t1!=se2.end()){
				int L=(*t1).second;
				int R=n;
				if(t2!=se1.end())R=(*t2).second-1;
				if(L<=R)addd(1,q,1,L,R,-1);
			}
		}
	}
	for(int i=1;i<=q;++i)printf("%d\n",ans[i]);
	return 0;
}