#include<bits/stdc++.h>
using namespace std;
namespace IO {
	constexpr int bufsize = 230005;
	char buf[bufsize], *f1, *f2;
	char gtchar() {return f1 == f2 && (f2 = buf + fread(f1 = buf, 1, bufsize, stdin)) == buf? EOF: *f1++;}
	template<typename T> void read(T &ret)
	{
		int f = ret = 0;
		char ch = gtchar();
		while(!isdigit(ch)) f = ch == '-', ch = gtchar();
		while(isdigit(ch)) ret = (ret << 3) + (ret << 1) + (ch ^ 48), ch = gtchar();
		if(f) ret = -ret;
	}
	template<typename T, typename ...t> void read(T &a, t &...b) {read(a), read(b...);}
}using IO::read;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
constexpr int maxn = 500005;
int n, q, a[maxn], ans[maxn];
mt19937 rnd(random_device{}() ^ (ull) new char);
vector<int> ins[maxn], pos[maxn];
set<pii> Q, L, R;
struct Q {
	int l, r, id;
	friend bool operator < (const Q &a, const Q &b) {return a.l == b.l? a.r > b.r: a.l < b.l;}
}qs[maxn];
struct segment_tree {
	struct node {
		pii mx;
		int tag;
		friend node operator + (const node &a, const node &b) {return {max(a.mx, b.mx), 0};}
	}s[maxn << 2];
	void pushup(int k) {s[k] = s[k << 1] + s[k << 1 | 1];}
	void add(int k, int delta) {s[k].tag += delta, s[k].mx.first += delta;}
	void pushdown(int k) {if(s[k].tag) add(k << 1, s[k].tag), add(k << 1 | 1, s[k].tag), s[k].tag = 0;}
	void build(int k, int sl, int sr)
	{
		if(sl == sr) return s[k] = {{-1, sl}, 0}, void();
		int mid = sl + sr >> 1;
		build(k << 1, sl, mid), build(k << 1 | 1, mid + 1, sr);
	}
	void modify_node(int k, int sl, int sr, int q, int val)
	{
		if(sl == sr) return s[k] = {{val, sl}, 0}, void();
		int mid = sl + sr >> 1;
		pushdown(k);
		q <= mid? modify_node(k << 1, sl, mid, q, val): modify_node(k << 1 | 1, mid + 1, sr, q, val);
		pushup(k);
	}
	pii query_max() {return s[1].mx;}
	void modify_add(int k, int sl, int sr, int ql, int qr, int delta)
	{
		if(ql <= sl && sr <= qr) return add(k, delta);
		int mid = sl + sr >> 1;
		pushdown(k);
		if(ql <= mid) modify_add(k << 1, sl, mid, ql, qr, delta);
		if(qr > mid) modify_add(k << 1 | 1, mid + 1, sr, ql, qr, delta);
		pushup(k);
	}
}tree;
struct BIT {//维护只保留 <= 枚举答案的数时，出现个数的前缀和
	int c[maxn];
	int lowbit(int x) {return x & -x;}
	void modify(int k, int x) {while(k <= n) c[k] += x, k += lowbit(k);}
	int query(int k)
	{
		int ret = 0;
		while(k) ret += c[k], k -= lowbit(k);
		return ret;
	}
}bit;
void update(int i)
{
	// printf("update %d\n", i);
	int val = bit.query(qs[i].r) - bit.query(qs[i].l - 1);
	tree.modify_node(1, 1, q, i, val);
	L.insert({qs[i].l, i});
	R.insert({qs[i].r, i});
}
void del(int pos)
{
	bit.modify(pos, -1);
	auto l = L.upper_bound({pos, maxn}), r = R.lower_bound({pos, 0});
	int nr = l == L.end()? q: (l->second - 1), nl = r == R.end()? 0: r->second;
	if(nl <= nr) tree.modify_add(1, 1, q, nl, nr, -1);
}
int main()
{
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	read(n, q);
	for(int i = 1; i <= n; i++) bit.c[i] = bit.lowbit(i);
	tree.build(1, 1, q);

	for(int i = 1; i <= n; i++) read(a[i]), pos[a[i]].push_back(i);
	for(int i = 1; i <= q; i++) read(qs[i].l, qs[i].r), qs[i].id = i;
	sort(qs + 1, qs + 1 + q);
	set<pii> tmp;
	for(int i = 1; i <= q; i++)
	{
		auto it = tmp.lower_bound({qs[i].r, 0});
		if(it != tmp.end()) ins[it->second].push_back(i);
		else update(i);
		tmp.insert({qs[i].r, i});
	}
	for(int i = 10; i >= 0; i--)
	{
		pii cur;
		// printf("%d\n", i);
		while((cur = tree.query_max()).first > i)
		{
			// printf("%d at %d\n", cur.first, cur.second);
			tree.modify_node(1, 1, q, cur.second, -1);
			ans[qs[cur.second].id] = i + 1;
			// printf("pop %d(%d)\n", cur.second, qs[cur.second].id);
			for(int j : ins[cur.second]) update(j);
		}
		for(int p : pos[i]) del(p);
		// printf("%d\n", i);
	}
	for(int i = 1; i <= q; i++) printf("%d\n", ans[i]);
	return 0;
}