#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct node{
	int l,r,pos,id;
}q[1000005];
int n,m,k,a[1000005],cnt[1000005],ans[1000005],sum[1000005];
int maxx=-1;
int cmp(node a,node b)
{
	if(a.pos==b.pos)
	{
		if(a.pos&1==0)
		{
			return a.r<b.r;
		}
		else
		{
			return a.r>b.r;
		}
	}
	return a.pos<b.pos;
}
void add(int x)
{
	sum[++cnt[a[x]]]++;
	if(cnt[a[x]]>maxx)
	{
		maxx=cnt[a[x]];
	}
	return ;
}
void del(int x)
{
	if(sum[cnt[a[x]]]==1&&maxx==cnt[a[x]])
	{
		maxx--;
	}
	sum[cnt[a[x]]--]--;
	return ;
}
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
	{
        if(ch=='-')
        {
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
	{
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int main()
{
	n=read();
	m=read();
	for(int i=1;i<=n;i++) 
	{
		a[i]=read();
	}
	int size=sqrt(n);
	for(int i=1;i<=m;i++)
	{
		q[i].l=read();
		q[i].r=read();
		q[i].pos=(q[i].l-1)/size+1;
		q[i].id=i;
	}
	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(--l);
		}
		while(r<q[i].r)
		{
			add(++r);
		}
		while(l<q[i].l)
		{
			del(l++);
		}
		while(r>q[i].r)
		{
			del(r--);
		}
		ans[q[i].id]=maxx;
	}
	for(int i=1;i<=m;i++)
	{
		printf("%d",ans[i]);
	}
	return 0;
}