#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(1731502166/*sd*/);

constexpr int N = 5E5 + 5;

constexpr int V = 5E5;

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

struct A {int min = 1E9;} ;
A operator+(A a, A b) {return A{std::min(a.min, b.min)};}

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

Fenwick<int> fen;
Fenwick<A> suf;

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 << ",l:" << b[t[x].idx].l << ",r:" << b[t[x].idx].r << ",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::cerr << "sd : " << sd << "\n";

	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 = 1; i <= q; ++i) {
	// 	std::cerr << b[i].l << " " << b[i].r << " " << b[i].idx << "\n";
	// }

	for (int i = q; i >= 1; --i) {
		auto p = suf.query(b[i].l).min;
		if (p == 1E9) {
			rt = merge(newnode(i, b[i].r - b[i].l + 1 - V), rt);
		} else {
			// std::cerr << p << " contain " << i << "\n";
			adj[p].push_back(i);
		}
		suf.add(b[i].l, (A){i});
	}

	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) {
		// std::cerr << "mex : " << mex << "\n";
		// debug(rt);
		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);
			// std::cerr << "del : " << i << "\n";
			// debug(rt);
			ans[b[i].idx] = mex + 1;
		}
		// std::cerr << "\n";
		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;
}