#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int read()
{
	int goal;
	char mid;
	mid=getchar();
	for(;mid<'0'||mid>'9';)
	{
		mid=getchar();
	}
	goal=0;
	for(;mid>='0'&&mid<='9';)
	{
		goal*=10;
		goal+=mid-'0';
		mid=getchar();
	}
	return goal;
}
struct make
{
	int id,l,r;
};
int block;
int num[300005];
int check[300005];
int check_check[300005];
int answer[300005];
make ask[300005];
int cmp(make one,make two)
{
	if(one.l/block==two.l/block)
	{
		return one.r<two.r;
	}
	return one.l/block<two.l/block;
}
int main()
{
	int n,q,left,right,big,kind_num;
	n=read();
	q=read();
	kind_num=0;
	block=sqrt(n);
	for(int i=0;i<n;i++)
	{
		num[i]=read();
		if(check[num[i]]==0)
		{
			check[num[i]]=1;
			kind_num++;
		}
	}
	memset(check,0,sizeof(check));
	for(int i=0;i<q;i++)
	{
		ask[i].id=i;
		ask[i].l=read();
		ask[i].r=read();
		ask[i].l--;
		ask[i].r--;
	}
	sort(ask,ask+q,cmp);
	left=0;
	right=0;
	check[num[0]]++;
	big=1;
	check_check[1]=1;
	check_check[0]=kind_num-1;
	for(int i=0;i<q;i++)
	{
		for(;right>ask[i].r;)
		{
			check[num[right]]--;
			check_check[check[num[right]]+1]--;
			if(check_check[big]==0)
			{
				big--;
			}
			check_check[check[num[right]]]++;
			right--;
		}
		for(;left<ask[i].l;)
		{
			check[num[left]]--;
			check_check[check[num[left]]+1]--;
			if(check_check[big]==0)
			{
				big--;
			}
			check_check[check[num[left]]]++;
			left++;
		}
		for(;right<ask[i].r;)
		{
			right++;
			check[num[right]]++;
			check_check[check[num[right]]-1]--;
			check_check[check[num[right]]]++;
			if(check_check[big+1]==1)
			{
				big++;
			}
		}
		for(;left>ask[i].l;)
		{
			left--;
			check[num[left]]++;
			check_check[check[num[left]]-1]--;
			check_check[check[num[left]]]++;
			if(check_check[big+1]==1)
			{
				big++;
			}
		}
		if(big<=(ask[i].r-ask[i].l+2)/2)
		{
			answer[ask[i].id]=1;
		}
		else
		{
			answer[ask[i].id]=big*2-(ask[i].r-ask[i].l+1);
		}
	}
	for(int i=0;i<q;i++)
	{
		printf("%d\n",answer[i]);
	}
	return 0;
}
