#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int now=0,nev=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')nev=-1;c=getchar();}
	while(c>='0'&&c<='9'){now=(now<<1)+(now<<3)+(c&15);c=getchar(); }
	return now*nev;
}

const int N = 3e5 + 5, lim = 1e5;
int S, a[N], n, m, ans[N];
int cnt[N], s[N], L, R, sum = 0;
int nw = 0;
int pos(int x){
	return (x - 1) / S + 1;
}
struct query{
	int l, r;
	int id;
	bool operator < (const query &Q) const{
		if (pos(l) != pos(Q.l)) return pos(l) < pos(Q.l);
		return r < Q.r;
	}
} q[N];

void add(int x){
	int kl = cnt[a[x] + lim];
	cnt[a[x] + lim] ++;
	s[kl] --, s[kl + 1] ++;
	if (kl + 1 > nw) nw = kl + 1;
}
void del(int x){
	int kl = cnt[a[x] + lim];
	s[kl] --, s[kl - 1] ++;
	cnt[a[x] + lim] --;
	if (s[kl] == 0) nw = kl - 1;
}

signed main()
{
	n = read(), m = read();
	S = sqrt(n);
	for (int i = 1; i <= n; i ++) a[i] = read();
	for (int i = 1; i <= m; i ++)
		q[i].l = read(), q[i].r = read(), q[i].id = i;
	sort(q + 1, q + m + 1);
	L = 1, R = 0;
	for (int i = 1; i <= m; i ++){
		int ql = q[i].l, qr = q[i].r;
		while (L < ql) del(L ++);
		while (R < qr) add(++ R);
		while (L > ql) add(-- L);
		while (R > qr) del(R --);
		ans[q[i].id] = nw;
	}
	for (int i = 1; i <= m; i ++)
		cout << ans[i] << "\n";
	return 0;
}

#2 #3 #4 #11 WA