#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

auto sd = std::time(0);
std::mt19937_64 g(sd);

constexpr int N = 5E5 + 5;

constexpr int V = 15;

int n, q, a[N], ans[N];
int suf[N];
std::vector<int> vec[N];

struct Fenwick {
	int sum[N];
	void add(int x, int val) {
		for (; x <= n; x += x & -x) {
			sum[x] += val;
		}
	}
	int query(int x) {
		int res = 0;
		for (; x; x -= x & -x) {
			res += sum[x];
		}
		return res;
	}
} fen;

struct Query {
	int l, r;
	int idx;
	bool operator<(const Query &w) const {
		return r == w.r ? l > w.l : r < w.r;
	}
} b[N];

std::vector<int> adj[N];

int rt, tot;

struct Data {
	int ls, rs;
	u64 rnd;
	int idx;
	int tag;
	int max, val, pos;
} t[N];

void pull(int x) {
	t[x].pos = t[x].idx;
	t[x].max = t[x].val;
	for (int y : {t[x].ls, t[x].rs}) {
		if (y && t[y].max > t[x].max) {
			t[x].max = t[y].max;
			t[x].pos = t[y].pos;
		}
	}
}
void apply(int x, int v) {
	if (!x) return ;
	t[x].max += v;
	t[x].val += v;
	t[x].tag += v;
}
void push(int x) {
	apply(t[x].ls, t[x].tag);
	apply(t[x].rs, t[x].tag);
	t[x].tag = 0;
}

void split(int x, int k, int &u, int &v, bool opt) {
	if (!x) {u = v = 0; return ;}
	push(x);
	int key = (!opt ? b[t[x].idx].l : b[t[x].idx].r);
	if (key <= k) split(t[x].rs, k, t[x].rs, v, opt), pull(u = x);
	else split(t[x].ls, k, u, t[x].ls, opt), pull(v = x);
}
int merge(int x, int y) {
	if (!x || !y) return x | y;
	push(x), push(y);
	if (t[x].rnd < t[y].rnd) {
		t[x].rs = merge(t[x].rs, y);
		return pull(x), x;
	} else {
		t[y].ls = merge(x, t[y].ls);
		return pull(y), y;
	}
}

int newnode(int i, int v) {
	int x = ++tot;
	t[x].ls = t[x].rs = t[x].tag = 0;
	t[x].idx = t[x].pos = i;
	t[x].max = t[x].val = v;
	t[x].rnd = g();
	return x;
}
void modify(int i, int val) {
	int x, y, z;
	split(rt, i - 1, x, y, 1);
	split(y, i, y, z, 0);
	apply(y, val);
	rt = merge(merge(x, y), z);
}
void insert(int i, int val) {
	int x, y;
	split(rt, b[i].l, x, y, 0);
	rt = merge(merge(x, newnode(i, val)), y);
}

int find(int &x) {
	if (!x) {
		return -1;
	}
	push(x);
	if (t[x].val == t[x].max) {
		int temp = x;
		x = merge(t[x].ls, t[x].rs);
		return temp;
	}
	int res;
	if (t[x].ls && t[t[x].ls].max == t[x].max) res = find(t[x].ls);
	else res = find(t[x].rs);
	return pull(x), res;
}

void debug(int x) {
	if (!x) return ;
	push(x);
	debug(t[x].ls);
	std::cerr << "x:" << x << ",ls:" << t[x].ls << ",rs:" << t[x].rs << ",idx:" << t[x].idx << ",val:" << t[x].val << ",max:" << t[x].max << "\n";
	debug(t[x].rs);
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> n >> q;

	for (int i = 1; i <= n; ++i) {
		std::cin >> a[i];
		vec[a[i]].push_back(i);
	}

	for (int i = 1; i <= q; ++i) {
		std::cin >> b[i].l >> b[i].r;
		b[i].idx = i;
	}

	std::sort(b + 1, b + 1 + q);

	for (int i = q; i >= 1; --i) {
		suf[i] = b[i].l;
		if (i < q) suf[i] = std::min(suf[i], suf[i + 1]);
	}

	for (int i = 1; i <= q; ++i) {
		auto check = [&](int j) {
			return j <= q && suf[j] <= b[i].l;
		} ;
		int l = i + 1, r = q;
		while (l < r) {
			int mid = (l + r + 1) / 2;
			if (check(mid)) l = mid;
			else r = mid - 1;
		}
		if (!check(l)) {
			rt = merge(rt, newnode(i, (b[i].r - b[i].l + 1) - V));
		} else {
			adj[l].push_back(i);
		}
	}

	// for (int i = 1; i <= q; ++i) {
	// 	std::cout << b[i].l << " " << b[i].r << " " << b[i].idx << "\n";
	// }
	// std::cerr << "\n";

	for (int i = 1; i <= n; ++i) {
		fen.sum[i]++;
		int j = i + (i & -i);
		if (j <= n)
			fen.sum[j] += fen.sum[i];
	}

	for (int mex = V; mex >= 0; --mex) {
		// debug(rt);
		// std::cerr << "\n";
		while (rt && t[rt].max > 0) {
			int node = find(rt);
			int i = t[node].idx;
			for (auto j : adj[i])
				insert(j, fen.query(b[j].r) - fen.query(b[j].l - 1) - mex);
			ans[b[i].idx] = mex + 1;
		}
		apply(rt, 1);
		for (auto i : vec[mex]) {
			fen.add(i, -1);
			modify(i, -1);
		}
	}

	for (int i = 1; i <= q; ++i) {
		std::cout << ans[i] << "\n";
	}

	return 0;
}