#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define getcha()(S==T&&(T=(S=fsr)+fread(fsr, 1, 1<<15, stdin), S==T)?EOF:*S++)
char fsr[1<<15], *S=fsr, *T=fsr;
const int MAXN=1e5;
inline int read(){
	int r(0),w(1);char ch;
	while(ch=getcha(), ch>=58 || ch<=47)w=(ch=='-'?-1:1);r=(r<<3)+(r<<1)+ch-48;
	while(ch=getcha(), ch<=57 && ch>=48)r=(r<<3)+(r<<1)+ch-48;
	return r*w;
}
struct node{
	int l, r, id;
}mp[(int)2e5+5];
int cnt[(int)2e5+5], ans[(int)2e5+5], lst[(int)2e5+5], tot[(int)2e5+5];
void add(int n, int m){
    tot[cnt[n]]--;
    tot[++cnt[n]]++;
    if(cnt[n]>ans[m]){ans[m]=cnt[n];}
}
void del(int n, int m){
	tot[cnt[n]]--;
    if(!tot[cnt[n]]){ans[m]=cnt[n]-1;}
    tot[--cnt[n]]++;
}
int block;
bool cmp(node n, node m){
	if(n.l/block!=m.l/block){return n.l/block<m.l/block;}
	return n.r/block<m.r/block;
}
signed main(){
	int n, m;
	n=read();m=read();
	block=sqrt(m);
	for(int i=1;i<=n;i++){lst[i]=read()+MAXN;}
	for(int i=1;i<=m;i++){mp[i].l=read();mp[i].r=read();mp[i].id=i;}
	std::sort(mp+1,mp+m+1,cmp);
	int left=1, right=0;
	for(int i=1;i<=m;i++){
		while(right<mp[i].r){add(lst[++right], mp[i].id);}
		while(right>mp[i].r){del(lst[right--], mp[i].id);}
		while(left<mp[i].l){del(lst[left++], mp[i].id);}
		while(left>mp[i].l){add(lst[--left], mp[i].id);}
        if(!ans[mp[i].id]){ans[mp[i].id]=ans[mp[i-1].id];}
	}
	for(int i=1;i<=m;i++){
		printf("%d\n", ans[i]);
	}
	return 0;
}