#include <bits/stdc++.h>
#define PB push_back
#define EB emplace_back
using namespace std;
const int maxn = 500000, V = 500000;
int n, Q;
int a[maxn + 5];
int t[maxn + 5];
void modify(int x, int v) {
	for (; x <= n; x += x & (-x)) t[x] += v;
}
int query(int x) {
	int rs = 0;
	for (; x; x -= x & (-x)) rs += t[x];
	return rs;
}
int query(int l, int r) { return query(r) - query(l - 1); }
int ti;
namespace SEG1 {
int mx[4 * maxn + 5], tg[4 * maxn + 5];
inline void mark(int p, int v) { mx[p] += v, tg[p] += v; }
inline void pushdown(int p) {
	if (tg[p]) {
		mark(p << 1, tg[p]), mark(p << 1 | 1, tg[p]);
		tg[p] = 0;
	}
}
inline void pushup(int p) { mx[p] = max(mx[p << 1], mx[p << 1 | 1]); }
void ins(int p, int l, int r, int x, int v) {
	if (l == r) return mx[p] = v, void();
	pushdown(p);
	int mid = (l + r) / 2;
	if (mid >= x) ins(p << 1, l, mid, x, v);
	else ins(p << 1 | 1, mid + 1, r, x, v);
	pushup(p);
}
void modify(int p, int l, int r, int x, int y) {
	if (x <= l && r <= y) return mark(p, -1);
	pushdown(p);
	int mid = (l + r) / 2;
	if (mid >= x) modify(p << 1, l, mid, x, y);
	if (mid < y) modify(p << 1 | 1, mid + 1, r, x, y);
	pushup(p);
}
int find(int p, int l, int r) {
	if (l == r) return l;
	pushdown(p);
	int mid = (l + r) / 2;
	if (mx[p << 1] > ti) return find(p << 1, l, mid);
	return find(p << 1 | 1, mid + 1, r); 
}
} // namespace SEG1
struct item {
	int r, id;
	bool operator<(const item& b) const {
		if (r == b.r) return id > b.id;
		return r < b.r;
	}
};
namespace SEG2 {
item mx[4 * maxn + 5];
item find(int p, int l, int r, int x, int y) {
	if (x <= l && r <= y) return mx[p];
	int mid = (l + r) / 2;
	item rs{0, 0};
	if (mid >= x) rs = max(rs, find(p << 1, l, mid, x, y));
	if (mid < y) rs = max(rs, find(p << 1 | 1, mid + 1, r, x, y));
	return rs;
}
inline void pushup(int p) { mx[p] = max(mx[p << 1], mx[p << 1 | 1]); }
void ins(int p, int l, int r, int x, item v) {
	if (l == r) return mx[p] = v, void();
	int mid = (l + r) / 2;
	if (mid >= x) ins(p << 1, l, mid, x, v);
	else ins(p << 1 | 1, mid + 1, r, x, v);
	pushup(p);
}
} // namespace SEG2
set<item> sl, sr;
vector<int> L[maxn + 5];
struct Query {
	int l, r, id;
	bool operator<(const Query& b) const {
		if (l == b.l) return r > b.r;
		return l < b.l;
	}
} q[maxn + 5];
void ins(int x) {
	SEG1::ins(1, 1, Q, x, query(q[x].l, q[x].r));
	sl.insert({q[x].l, x}), sr.insert({q[x].r, x});
}
int ans[maxn + 5];
int main() {
	scanf("%d%d", &n, &Q);
	for (int i = 1, a; i <= n; i++) {
		scanf("%d", &a);
		L[a].PB(i);
		modify(i, 1);
	}
	for (int i = 1; i <= Q; i++) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
	sort(q + 1, q + Q + 1);
	memset(SEG1::mx, -1, sizeof(SEG1::mx));
	for (int i = 1, r = 0; i <= Q; i++) {
		if (q[i].r > r) {
			r = q[i].r;
			ins(i);
		} else SEG2::ins(1, 1, Q, i, {q[i].r, i});
	}
	for (ti = V; ~ti; ti--) {
		for (int x : L[ti + 1]) {
			modify(x, -1);
			auto ir = sr.lower_bound({x, (int)1E9}), il = sl.upper_bound({x, 0});
			if (ir == sr.end() || il == sl.begin()) continue;
			SEG1::modify(1, 1, Q, prev(il)->id, ir->id);
		}
		while (SEG1::mx[1] > ti) {
			int x = SEG1::find(1, 1, Q);
			SEG1::ins(1, 1, Q, x, -1E9);
			auto it = sr.find({q[x].r, x});
			int y = next(it) == sr.end() ? Q : next(it)->id, l = it == sr.begin() ? 0 : prev(it)->r;
			sl.erase({q[x].l, x}), sr.erase(it);
			while (x < y) {
				auto rs = SEG2::find(1, 1, Q, x, y);
				if (rs.r <= l) break;
				ins(y = rs.id);
				SEG2::ins(1, 1, Q, y, {0, 0});
			}
			ans[q[x].id] = ti + 1;
		}
	}
	for (int i = 1; i <= Q; i++) printf("%d\n", ans[i]);
}