#include <bits/stdc++.h>

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

constexpr int N = 5E5 + 5;

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

template<class Info, class Tag>
class LazySegmentTree {
public:
	int n;
	std::vector<Info> t;
	std::vector<Tag> tag;
	LazySegmentTree() {}
	LazySegmentTree(int _n) {
		init(_n, std::vector<Info>(n, {}));
	}
	LazySegmentTree(int _n, std::vector<Info> a) {
		init(_n, a);
	}
	void pull(int x) {t[x] = t[x * 2] + t[x * 2 + 1];}
	void init(int _n, std::vector<Info> a) {
		n = _n;
		t.assign((n + 1) << 2, {});
		tag.assign((n + 1) << 2, {});
		std::function<void(int, int, int)> build = [&](int x, int l, int r) {
			if (l == r) {
				t[x] = a[l];
				return ;
			}
			int mid = (l + r) / 2;
			build(x * 2, l, mid);
			build(x * 2 + 1, mid + 1, r);
			pull(x);
		} ;
		build(1, 1, n);
	}
	void apply(int x, Tag v) {
		t[x].apply(v);
		tag[x].apply(v);
	}
	void push(int x) {
		apply(x * 2, tag[x]);
		apply(x * 2 + 1, tag[x]);
		tag[x] = {};
	}
	void modify(int x, int l, int r, int L, int R, Tag v) {
		if (r < L || l > R) return ;
		if (l >= L && r <= R) return apply(x, v);
		int mid = (l + r) / 2; push(x);
		modify(x * 2, l, mid, L, R, v);
		modify(x * 2 + 1, mid + 1, r, L, R, v);
		pull(x);
	} ;
	void modify(int L, int R, Tag v) {modify(1, 1, n, L, R, v);}
	void modify(int pos, Tag v) {modify(pos, pos, v);}
	void change(int x, int l, int r, int pos, Info v) {
		if (l == r) return void(t[x] = v);
		int mid = (l + r) / 2; push(x);
		if (pos <= mid) change(x * 2, l, mid, pos, v);
		else change(x * 2 + 1, mid + 1, r, pos, v);
		pull(x);
	}
	void change(int pos, Info v) {change(1, 1, n, pos, v);}
	Info query(int x, int l, int r, int L, int R) {
		if (r < L || l > R) return {};
		if (l >= L && r <= R) return t[x];
		int mid = (l + r) / 2; push(x);
		return query(x * 2, l, mid, L, R) + query(x * 2 + 1, mid + 1, r, L, R);
	}
	Info query(int L, int R) {return query(1, 1, n, L, R);}
} ;
struct Tag {
	int tag = 0;
	void apply(const Tag &v) {tag += v.tag;}
} ;
struct Info {
	int max = -1E9, pos = 0;
	void apply(const Tag &v) {max += v.tag;}
} ;
Info operator+(Info a, Info b) {
	return (Info) {
		std::max(a.max, b.max),
		a.max > b.max ? a.pos : b.pos
	} ;
}

LazySegmentTree<Info, Tag> seg1, seg2;

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 &p) const {
		return l == p.l ? r > p.r : l < p.l;
	}
} b[N];

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);

	std::vector<Info> init(q + 1);
	int max = 0;
	std::set<std::array<int, 2>> pl, pr;
	for (int i = 1; i <= q; ++i) {
		if (max < b[i].r) {
			max = b[i].r;
			pl.insert({b[i].l, i});
			pr.insert({b[i].r, i});
			init[i].max = b[i].r - b[i].l + 1 - n;
		}
		init[i].pos = i;
	}
	seg1.init(q, init);

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

	for (int i = 1; i <= q; ++i) {
		if (init[i].max == -1E9) init[i].max = b[i].r;
		else init[i] = {};
		init[i].pos = i;
	}
	seg2.init(q, init);

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

	for (int mex = n; mex >= 0; --mex) {
		// std::cerr << "mex : " << mex << "\n";
		while (seg1.query(1, q).max > 0) {
			int pos = seg1.query(1, q).pos;
			seg1.change(pos, (Info){(int)-1E9, pos});
			// std::cerr << "pos : " << pos << "!\n";
			auto it = pr.lower_bound({b[pos].r, pos});
			int tR = (it == pr.begin() ? 0 : (*std::prev(it))[0]);
			int nR = (std::next(it) == pr.end() ? n + 1 : (*std::next(it))[1]);
			// std::cerr << "tR : " << tR << " , nR : " << nR << "\n";
			ans[b[pos].idx] = mex + 1;
			pr.erase(it);
			pl.erase(pl.lower_bound({b[pos].l, pos}));
			while (true) {
				int np = seg2.query(pos + 1, nR - 1).pos;
				if (b[np].r > tR) {
					pl.insert({b[np].l, np});
					pr.insert({b[np].r, np});
					seg2.change(np, (Info){(int)-1E9, np});
					seg1.change(np, (Info){fen.query(b[np].r) - fen.query(b[np].l - 1) - mex, np});
					nR = np;
				} else break;
			}
		}
		seg1.modify(1, q, (Tag){1});
		for (auto i : vec[mex]) {
			fen.add(i, -1);
			auto itr = pr.lower_bound({i, 0});
			if (itr == pr.end()) continue;
			auto itl = pl.upper_bound({i, (int)1E9});
			if (itl == pl.begin()) continue;
			int r = (*std::prev(itl))[1], l = (*itr)[1];
			// std::cerr << "l : " << l << " , r : " << r << "\n";
			seg1.modify(l, r, (Tag){-1});
		}
	}

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

	return 0;
}