// Problem: Frequent values
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/UVA11235
// Memory Limit: 0 MB
// Time Limit: 3000 ms
// Date: 2024/11/21 20:12:18
// Author: Li_Feiy

#include <bits/stdc++.h>
#define arrout(a, n) rep(i, 1, n) printl(a[i])
#define arrin(a, n) rep(i, 1, n) a[i] = read()
#define rep(i, x, n) for(int i = x; i <= n; i++)
#define dep(i, x, n) for(int i = x; i >= n; i--)
#define erg(i, x) for(int i = head[x]; i; i = e[i].nex)
#define dbg(x) std::cout << #x << ":" << x << " "
#define mem(a, x) memset(a, x, sizeof a)
#define all(x) x.begin(), x.end()
#define arrall(a, n) a + 1, a + 1 + n
#define PII std::pair<int, int>
#define m_p std::make_pair
#define u_b upper_bound
#define l_b lower_bound
#define p_b push_back
#define CD const double
#define CI const int
#define int long long
#define il inline
#define ss second
#define ff first
#define itn int
int read() {
	char ch = getchar();
	int r = 0, w = 1;
	while(ch < '0' || ch > '9') w = ch == '-' ? -1 : w, ch = getchar();
	while(ch >= '0' && ch <= '9') r = (r << 3) + (r << 1) + (ch ^ 48), ch = getchar();
	return r * w;
}

void print(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x >= 10) print(x / 10);
	putchar(x % 10 + '0');
}template<typename ...Args>
void print(int t, Args... args) { print(t), print(args...); }

void printl(int x) { print(x), putchar('\n'); }
template<typename ...Args>
void printl(int t, Args... args) { printl(t), printl(args...); }

void printk(int x) { print(x), putchar(' '); }
template<typename ...Args>
void printk(int t, Args ... args) { printk(t), printk(args...); }

CI N = 2e5 + 5;
int n, q, t, ma, a[N], ans[N], blk[N];
std::unordered_map<int, int> cnt, vis;
struct Query {
	int l, r, id;
	bool operator<(const Query& b) const { return blk[l] == blk[b.l] ? r < b.r : blk[l] < blk[b.l]; }
} qu[N];
void pre() {
	t = n / pow(n, 0.5);
	rep(i, 1, t) rep(j, (i - 1) * t, i * t) blk[j] = i;
	std::sort(arrall(qu, q));
}
void add(int x) {
	cnt[vis[a[x]]] --, vis[a[x]] ++, cnt[vis[a[x]]] ++;
	if(vis[a[x]] > ma) ma = vis[a[x]];
}
void minus(int x) {
	cnt[vis[a[x]]] --, vis[a[x]] --, cnt[vis[a[x]]] ++;
	if(vis[a[x]] == ma - 1) ma = cnt[ma] ? ma : vis[a[x]];
}
signed main() {
	while(n = read(), n) {
		cnt.clear(), vis.clear();
		q = read();
		arrin(a, n);
		rep(i, 1, q) qu[i] = (Query) { read(), read(), i };
		pre();
		int l = 1, r = 0;
		rep(i, 1, q) {
			while(qu[i].l < l) add(-- l);
			while(qu[i].r > r) add(++ r);
			while(qu[i].l > l) minus(l ++);
			while(qu[i].r < r) minus(r --);
			ans[qu[i].id] = ma;
		}
		arrout(ans, q);
	}
	return 0;
}