救救蒟蒻

#include<bits/stdc++.h>
#define il inline
#define rint register int
using namespace std;
struct node{
	int l,r,id;
}q[200020];
int ans[200020],lsh[200020],a[200020],cnt[200020],t[200020],maxn,l,r,ql,qr,d,n,m,len;
il int read(){
	int ans=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')ans=ans*10+ch-'0',ch=getchar();
	return ans*f;
}
il void del(int x){
	t[cnt[a[x]]]--;
	if(t[cnt[a[x]]]==1&&cnt[a[x]]==maxn) maxn--;
	t[--cnt[a[x]]]++;
}
il void add(int x){
	t[cnt[a[x]]]--;
	t[++cnt[a[x]]]++;
	maxn=max(cnt[a[x]],maxn);
}
il bool cmp(node a,node b){
	return (a.l/d)^(b.l/d)?a.l<b.l:(((a.l/d)&1)?a.r<b.r:a.r>b.r);
}
signed main(){
    n=read();m=read();
    d=n/sqrt(m*2/3);
	for(rint i=1;i<=n;i++) a[i]=lsh[i]=read();
	sort(lsh+1,lsh+n+1);len=unique(lsh+1,lsh+1+m)-lsh-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(lsh+1,lsh+len+1,a[i])-lsh;
	}
	for(rint i=1;i<=m;i++){
		q[i].l=read();
		q[i].r=read();
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	for(rint i=1;i<=n;i++){
		ql=q[i].l,qr=q[i].r;
		while(l<ql)del(l++);
		while(l>ql)add(--l);
		while(r<qr)add(++r);
		while(r>qr)del(r--);
		ans[q[i].id]=-maxn;
	}
	for(rint i=1;i<=m;i++) printf("%d\n",ans[i]);
}