#include <bits/stdc++.h>
using namespace std;

const int N=4e5+5;

int n,m,siz;
int x[N],num[N],ind,ans[N],bl[N];
int l,r;
struct query{
	int id,l,r;
}q[N];

bool cmp(query a,query b){
	if(bl[a.l]==bl[b.l]){
		if(bl[a.l]&1) return a.r<b.r;
		else return a.l>b.l;
	}
	return bl[a.l]<bl[b.l];
}

int res,cnt[N],t[N];

void add(int w){
	cnt[w]++;
	if(cnt[w]>res){
		res=cnt[w];
	}
	t[cnt[w]-1]--;
	t[cnt[w]]++;
}

void del(int w){
	if(cnt[w]==res){
		if(t[res]==1){
			res--;
		}
	}
	t[cnt[w]]--;
	t[cnt[w]-1]++;
	cnt[w]--;
}

int main(){
	cin>>n>>m;
	siz=sqrt(n)+1;
	for(int i=1;i<=n;i++){
		scanf("%d",&x[i]);
		num[++ind]=x[i];
		bl[i]=(i-1)/siz+1;
	}
	sort(num+1,num+ind+1);
	ind=unique(num+1,num+ind+1)-num-1;
	for(int i=1;i<=n;i++){
		x[i]=lower_bound(num+1,num+ind+1,x[i])-num;
	}
	
	for(int i=1;i<=m;i++){
		scanf("%d%d",&l,&r);
		q[i]={i,l,r};
	}
	sort(q+1,q+m+1,cmp);
	
	int L=1,R=0;
	for(int i=1;i<=m;i++){
		while(L>q[i].l) add(x[--L]);
		while(L<q[i].l) del(x[L++]);
		while(R>q[i].r) del(x[R--]);
		while(R<q[i].r) add(x[++R]);
		ans[q[i].id]=res;
	}
	
	for(int i=1;i<=m;i++){
		printf("%d\n",-ans[i]);
	}
}