#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,block=720;
int a[N],lsh[N],at[N],belong[N],cnt[N],f[block][block],n,m,last;
vector<int>in[N];
struct Block{
	int l,r;
}b[block];

struct nodee{
	struct node{
	int l;
	int r;
	int w;
	int key;
	int siz;
	bool flag;
}e[100010];

int cnt,rt;

int newnode(int w){
	cnt ++;
	e[cnt].w = w;
	e[cnt].siz = 1;
	return cnt; 
}

void update(int i){
	e[i].siz = e[e[i].l].siz + e[e[i].r].siz + 1;
}

void pushdown(int i){
	swap(e[i].l,e[i].r);
	e[e[i].l].flag ^= 1;
	e[e[i].r].flag ^= 1;
	e[i].flag = false;
}

void split(int i,int siz,int &x,int &y){
	if(!i){
		x = y = 0;
		return ;
	}
	if(e[i].flag)pushdown(i);
	if(e[e[i].l].siz < siz){
		x = i;
		split(e[i].r,siz - e[e[i].l].siz - 1,e[i].r,y);
	}
	else {
		y = i;
		split(e[i].l,siz,x,e[i].l);
	}
	update(i);
}

int merge(int x,int y){
	if(!x || !y)return x + y;
	if(e[x].key < e[y].key){
		if(e[x].flag)pushdown(x);
		e[x].r = merge(e[x].r,y);
		update(x);
		return x;
	}
	else {
		if(e[y].flag)pushdown(y);
		e[y].l = merge(x,e[y].l);
		update(y);
		return y;
	}
}
};

int read(){
   int s = 0,w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
   while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
   return s * w;
}

int query(int len,int x){
	if (x<=(len+1)/2) return 1;
	int t=len-x;
	len-=2*t+1;
	return len+1;
}

inline int ask(int l,int r){
	int bl=belong[l],br=belong[r],ans=0;
	if(bl==br){
		for(int i=l;i<=r;i++){
			ans=max(ans,++cnt[a[i]]);
		}
		for(int i=l;i<=r;i++){
			cnt[a[i]]=0;
		}
	}else{
		ans=f[bl+1][br-1];
		for(int i=l;i<=b[bl].r;i++){
			for(int pos=at[i];pos+ans<in[a[i]].size()&&in[a[i]][pos+ans]<=r;ans++); 
		}
		for(int i=b[br].l;i<=r;i++){
			for(int pos=at[i];pos-ans>=0&&in[a[i]][pos-ans]>=l;ans++); 
		}
	}
	return ans;
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		a[i]=lsh[i]=read();
	}
	sort(lsh+1,lsh+n+1);
	int sz=unique(lsh+1,lsh+n+1)-lsh;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(lsh+1,lsh+sz,a[i])-lsh;
		in[a[i]].push_back(i);
		at[i]=in[a[i]].size()-1;
	}
	int c=0;
	for(int i=1;i<=n;i+=block){
		c++;
		b[c].l=i;
		b[c].r=min(i+block-1,n);
	}
	for(int i=1;i<=c;i++){
		int ans=0;
		for(int j=b[i].l;j<=b[i].r;j++){
			belong[j]=i;
		}
		for(int j=i;j<=c;j++){
			for(int k=b[j].l;k<=b[j].r;k++){
				ans=max(ans,++cnt[a[k]]);
			}
			f[i][j]=ans;
		}
		for(int j=i;j<=c;j++){
			for(int k=b[j].l;k<=b[j].r;k++){
				cnt[a[k]]=0;
			}
		}
	}
	while(m--){
		int l=read(),r=read();
		printf("%d\n",query(r - l + 1,ask(l,r)));
	}
    return 0;
}