#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[300005],pos[300005],ans;
int sum[300005],num[300005],Ans[300005];
struct query{
	int l,r,id,ans;
};query q[300005];
bool cmp(query a,query b){
    return pos[a.l]==pos[b.l]?a.r<b.r:pos[a.l]<pos[b.l];
}
bool cmp2(query a,query b){
	return a.id<b.id;
} 
void add(int x) {
    --sum[num[a[x]]], ++sum[++num[a[x]]];
    while (sum[ans + 1]) ++ans;
}

void del(int x) {
    --sum[num[a[x]]],++sum[--num[a[x]]];
    while (!sum[ans]) --ans;
}
int main(){
	cin>>n>>m;
	int siz=sqrt(n);
	for(int i=1;i<=n;i++){
		pos[i]=i/siz;
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&q[i].l,&q[i].r);q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	ans=0,sum[0]=1,num[0]=1;
	for(int i=1;i<=m;i++){
		int ql=q[i].l,qr=q[i].r;
		while(r<qr) add(++r);
		while(r>qr) del(r--);
		while(l<ql) del(l++);
		while(l>ql) add(--l);
		q[i].ans=max(1,2*ans-(qr-ql+1));
		Ans[q[i].id]=max(1,2*ans-(qr-ql+1));
	}
	sort(q+1,q+m+1,cmp2);
	for(int i=1;i<=m;i++){
		printf("%d\n",q[i].ans);
	} 
} 
/*
5 5
1 1 1 1 1
1 1
1 2 
1 3
1 4 
1 5
*/