// MagicDark
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define ls num << 1
#define rs ls | 1
#define li ls, l, mid
#define ri rs, mid + 1, r
#define debug cerr << "\33[32m[" << __LINE__ << "]\33[m "
#define SZ(x) ((int) x.size() - 1)
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
template <typename T> T& read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = - f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x *= f;
}
const int N = 5e5 + 10, inf = 1e9;
int n, q, a[N], ans[N], l[N], r[N], id[N];
vector <int> v[N], vv[N];
int info[N << 2], mx[N << 2], tag[N << 2];
set <pair <int, int>> s1, s2;
void pushup1(int num) {
	info[num] = max(info[ls], info[rs]);
}
void pushup2(int num) {
	mx[num] = max(mx[ls], mx[rs]);
}
void build(int num, int l, int r) {
	mx[num] = - inf;
	if (l == r) {
		info[num] = v[l].size() ? ::r[v[l].back()] : 0;
		return;
	}
	build(li), build(ri);
	pushup1(num);
}
struct BIT {
	int t[N];
	void add(int x, int y) {
		for (; x <= n; x += x & - x) t[x] += y;
	}
	int query(int x) {
		int s = 0;
		for (; x; x ^= x & - x) s += t[x];
		return s;
	}
	int query(int l, int r) {
		return query(r) - query(l - 1);
	}
} bt;
int pos;
void down(int num, int x) {
	tag[num] += x;
	mx[num] += x;
}
void pushdown(int num) {
	if (tag[num]) down(ls, tag[num]), down(rs, tag[num]), tag[num] = 0;
}
void change(int num, int l, int r, int L, int R, int x) {
	if (L <= l && r <= R) return down(num, x);
	pushdown(num);
	if (mid >= L) change(li, L, R, x);
	if (mid < R) change(ri, L, R, x);
	pushup2(num);
}
void ins(int l, int r) {
	// debug << "! " << l << " " << r << endl;
	s1.emplace(l, r);
	s2.emplace(r, l);
}
void bot(int num, int l, int r, int L, int R) {
	if (info[num] <= pos) return;
	if (l == r) {
		pos = info[num];
		mx[num] = bt.query(l, info[num]);
		id[l] = v[l].back();
		// debug << "@ " << l << " " << info[num] << endl;
		ins(l, info[num]);
		// s1.emplace(l, info[num]);
		// s2.emplace(info[num], l);
		v[l].pop_back();
		info[num] = v[l].size() ? ::r[v[l].back()] : 0;
		return;
	}
	if (mid >= L) bot(li, L, R);
	if (mid < R) bot(ri, L, R);
	pushup2(num);
}
vector <int> gg;
void del(int l, int r) {
	// debug << "! " << l << " " << r << endl;
	gg.push_back(l);
	assert(s1.erase(make_pair(l, r)));
	assert(s2.erase(make_pair(r, l)));
}
void qq(int num, int l, int r, int o) {
	if (mx[num] < o) return;
	if (l == r) {
		del(l, ::r[id[l]]);
		mx[num] = - inf;
		ans[id[l]] = o;
		return;
	}
	pushdown(num);
	qq(li, o), qq(ri, o);
	pushup2(num);
}
signed main() {
	read(n), read(q);
	F(i, 1, n) vv[read(a[i])].push_back(i), bt.add(i, 1);
	F(i, 1, q) {
		read(l[i]), read(r[i]);
		// debug << "@ " << l[i] << " " << r[i] << endl;
		v[l[i]].push_back(i);
	}
	F(i, 1, n) sort(all(v[i]), [&] (int x, int y) {
		return r[x] < r[y];
	});
	// debug << v[2].size() << endl;
	ins(0, 0), ins(n + 1, n + 1);
	build(1, 1, n);
	bot(1, 1, n, 1, n);
	DF(i, n, 0) {
		for (int j: vv[i]) {
			bt.add(j, - 1);
			auto it = s2.lower_bound(make_pair(j, 0));
			int p = it -> second;
			if (p <= j) change(1, 1, n, p, j, - 1);
		}
		while (true) {
			gg.clear();
			qq(1, 1, n, i);
			if (gg.empty()) break;
			for (int j: gg) {
				auto i2 = s1.lower_bound(make_pair(j, inf));
				auto i1 = prev(i2);
				// if (j < i2 -> first) {
				pos = i1 -> second;
				bot(1, 1, n, j, i2 -> first - 1);
				// }
			}
		}
	}
	F(i, 1, q) cout << ans[i] << '\n';
	return 0;
}
/* why?
*/