#include<bits/stdc++.h>
using namespace std;
struct node
{
    int id,l,r;
}q[114514*2];
int maxn;
int ans[114514*2];
int n,m,a[114514*2];
int size,belong[114514*2],l=1,r,cnt[114514*2],t[114514*2],b[114514];
bool cmp(node x,node y)
{
    if(belong[x.l]==belong[y.l])
        return x.r<y.r;
    return belong[x.l]<belong[y.l];
}
void add(int x)
{
    t[cnt[a[x]]]--;
    t[++cnt[a[x]]]++;
    maxn=max(maxn,cnt[a[x]]);
}
void del(int x)
{
    t[cnt[a[x]]]--;
    if(maxn==cnt[a[x]]&&!t[cnt[a[x]]])
        maxn--;
    t[--cnt[a[x]]]++;
}
int main()
{
    cin>>n>>m;
    size=sqrt(n);
    for(int i=1;i<=n;i++)
    	cin>>a[i],b[i]=a[i];
    sort(b+1,b+n+1);
	int sum=unique(b+1,b+1+n)-b;
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(b+1,b+1+sum,a[i])-b;
    for(int i=1;i<=n;i++)
        belong[i]=i/size+1;
    for(int i=1;i<=m;i++)
        cin>>q[i].l>>q[i].r,q[i].id=i;
    sort(q+1,q+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        while(l<q[i].l)
            del(l++);
        while(l>q[i].l)
            add(--l);
        while(r<q[i].r)
            add(++r);
        while(r>q[i].r)
            del(r--);
        ans[q[i].id]=maxn;
    }
    for(int i=1;i<=m;i++)
        cout<<-ans[i]<<endl;
}