#include<bits/stdc++.h>
using namespace std;
struct nd{
	int val,id;
	bool operator<(nd a){
		return val<a.val;
	}
}b[500010];
int n,s,m,q,a[500010],g[500010],l,r,ans,c;
int cnt[500010],t[720][720],res;
vector<int> v[500010];
inline int sk(int x){
	return (x-1)*s+1;
}
inline int ek(int x){
 	return min(x*s,n);
}
int main(){
	scanf("%d%d",&n,&q);
	s=sqrt(n);
	m=(n+s-1)/s;
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i].val);
		b[i].id=i;
	} 
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++){
		if(b[i].val!=b[i-1].val) c++;
		a[b[i].id]=c;
	}
	for(int i=1;i<=m;i++){
		memset(cnt,0,sizeof(cnt));
		res=0;
		for(int j=i;j<=m;j++){
			for(int k=sk(j);k<=ek(j);k++){
				cnt[a[k]]++;
				if(cnt[a[k]]>res) res=cnt[a[k]];
			}
			t[i][j]=res;
		}
	}
	for(int i=1;i<=n;i++){
		g[i]=v[a[i]].size();
		v[a[i]].push_back(i);		
	}
	while(q--){
		scanf("%d%d",&l,&r);
		int lp=(l+s)/s,rp=r/s;
		if(r==n) rp=m;
		ans=t[lp][rp];
		for(int i=l;i<sk(lp);i++){
			if(g[i]+ans<=int(v[a[i]].size())-1&&v[a[i]][g[i]+ans]<=r) ans++;
		}
		for(int i=ek(rp)+1;i<=r;i++){
			if(g[i]-ans>=0&&v[a[i]][g[i]-ans]>=l) ans++;
		}
		printf("-%d\n",ans);
	}
}