#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int N = 5e5 + 10;

int n, m, a[N];

struct Bit {
	int bt[N];
	void upd(int x, int v) {while (x <= n) {bt[x] += v; x += x & -x;}}
	int qry(int x) {int res = 0; while (x) {res += bt[x]; x -= x & -x;} return res;}
	int qry(int l, int r) {return qry(r) - qry(l - 1);}
} bit;

struct Query {int l, r, id;} q[N];

struct Node {int mx, tag, ls, rs;} t[N << 4]; int tot;
struct Seg {
#define mid (l + r >> 1)
#define lrt (t[rt].ls)
#define rrt (t[rt].rs)
#define MAXN m + 1
	int Rt;
	void pushr(int rt, int v) {t[rt].mx += v; t[rt].tag += v;}
	void pushdown(int rt) {
		if (t[rt].tag) {
			if (lrt) pushr(lrt, t[rt].tag);
			if (rrt) pushr(rrt, t[rt].tag);
			t[rt].tag = 0;
		}
	}

	void build(int *a, int l, int r, int &rt) {
		if (!rt) rt = ++tot;
		if (l == r) {t[rt].mx = a[l]; return ;}
		build(a, l, mid, lrt); build(a, mid + 1, r, rrt);
		t[rt].mx = max(t[lrt].mx, t[rrt].mx);
	}
	void build(int *a) {build(a, 1, MAXN, Rt);}

	void upd(int ll, int rr, int v, int l, int r, int rt) {
		if (ll > rr) return ;
		if (ll <= l && r <= rr) {pushr(rt, v); return ;}
		pushdown(rt);
		if (ll <= mid) upd(ll, rr, v, l, mid, lrt);
		if (mid < rr) upd(ll, rr, v, mid + 1, r, rrt);
		t[rt].mx = max(t[lrt].mx, t[rrt].mx);
	}
	void upd(int ll, int rr, int v) {upd(ll, rr, v, 1, MAXN, Rt);}

	void chg(int p, int v, int l, int r, int rt) {
		if (l == r) {t[rt].mx = v; return ;}
		pushdown(rt);
		if (p <= mid) chg(p, v, l, mid, lrt);
		else chg(p, v, mid + 1, r, rrt);
		t[rt].mx = max(t[lrt].mx, t[rrt].mx);
	}
	void chg(int p, int v) {chg(p, v, 1, MAXN, Rt);}

	int qry(int ll, int rr, int l, int r, int rt) {
		if (ll > rr) return 0;
		if (ll <= l && r <= rr) return t[rt].mx;
		pushdown(rt);
		if (rr <= mid) return qry(ll, rr, l, mid, lrt);
		if (mid < ll) return qry(ll, rr, mid + 1, r, rrt);
		return max(qry(ll, rr, l, mid, lrt), qry(ll, rr, mid + 1, r, rrt));
	}
	int qry(int ll = 1, int rr = MAXN) {return qry(ll, rr, 1, MAXN, Rt);}

	int find(int k, int l, int r, int rt) {
		if (l == r) {return l;}
		pushdown(rt);
		if (t[lrt].mx > k) return find(k, l, mid, lrt);
		else return find(k, mid + 1, r, rrt);
	}
	int find(int k) {return find(k, 1, MAXN, Rt);}

	int del(int l, int r, int rt) {
		if (l == r) {t[rt].mx = -1e9; return l;}
		pushdown(rt); int res;
		if (t[lrt].mx == t[rt].mx) res = del(l, mid, lrt);
		else if (t[rrt].mx == t[rt].mx) res = del(mid + 1, r, rrt);
		else res = -1;
		t[rt].mx = max(t[lrt].mx, t[rrt].mx);
		return res;
	}
	int del() {return del(1, MAXN, Rt);}
} mx, seg;

int pmx[N], r[N], v[N], ans[N];
vector <int> pos[N];
int Maxval;
vector <int> live;
bool cmp(int A, int B) {return q[A].l ^ q[B].l ? q[A].l < q[B].l : q[A].r < q[B].r;}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		Maxval = max(Maxval, a[i]);
		pos[a[i]].push_back(i);
		bit.upd(i, 1);
	}
	for (int i = 1; i <= m; ++i)
		cin >> q[i].l >> q[i].r, q[i].id = i;
	sort(q + 1, q + m + 1, [](Query A, Query B) {return A.l ^ B.l ? A.l < B.l : A.r > B.r;});
	for (int i = 1; i <= m; ++i) {
		r[i] = q[i].r;
		pmx[i] = max(pmx[i - 1], q[i].r);
		if (q[i].r > pmx[i - 1]) live.push_back(i);
		v[i] = q[i].r > pmx[i - 1] ? q[i].r - q[i].l + 1 : -1e9;
	}
	r[m + 1] = -1e9; mx.build(r); v[m + 1] = -1e9; seg.build(v);
	for (int i = Maxval * 2; i >= 0; --i) {
		// cout << " " << i << endl;
		// if (pos[i].empty()) continue;
		for (int p : pos[i]) {
			bit.upd(p, -1); q[m + 1] = {p, 0};
			int l = lower_bound(live.begin(), live.end(), m + 1, [](int A, int B) {return q[A].r < q[B].r;}) - live.begin();
			q[m + 1].r = n + 1;
			int r = lower_bound(live.begin(), live.end(), m + 1, cmp) - live.begin() - 1;
			while (0 <= l && l < live.size() && q[live[l]].r < p && l <= r) ++l;
			while (0 <= r && r < live.size() && q[live[r]].l > p && l <= r) --r;
			if (l > r) continue;
			l = live[l]; if (r >= 0) r = live[r];
			seg.upd(l, r, -1);
		}
		while (seg.qry() >= i) {
			int x = seg.del();
			ans[q[x].id] = i;
			mx.chg(x, -1e9);
			vector <int>::iterator it = lower_bound(live.begin(), live.end(), x, cmp);
			int lst, nxt, val;
			if (it - live.begin() > 0) lst = live[it - live.begin() - 1];
			else lst = 0;
			if (it - live.begin() == live.size() - 1) nxt = n + 1;
			else nxt = live[it - live.begin() + 1];
			live.erase(it);
			while (mx.find(r[lst]) != m + 1 && (live.empty() || lower_bound(live.begin(), live.end(), mx.find(r[lst]), cmp) == live.end() || *lower_bound(live.begin(), live.end(), mx.find(r[lst]), cmp) != nxt)) {
				val = mx.find(r[lst]);
				// if (lst == val) break;
				live.insert(lower_bound(live.begin(), live.end(), val, cmp), val);
				seg.chg(val, bit.qry(q[val].l, q[val].r));
				lst = val;
			}
		}
	}
	for (int i = 1; i <= m; ++i)
		cout << ans[i] << endl;
	return 0;
}