#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e5 + 5;
const int inf = 0x3f3f3f3f;
const int ninf = ~0x3f3f3f3f; 

struct Pair {
	int x, y;
	Pair (int _x = ninf, int _y = ninf) :
		x(_x), y(_y) {}
};
bool operator<(Pair u, Pair v) {
	return u.x < v.x;
}

int n, m;
int a[N] = {0};

struct BIT {
	int t[N] = {0};
	BIT () {}
	void init() {
		for (int i = 1; i <= n; i++)
			t[i] = 0;
	}
	int lowbit(int x) {
		return x & -x;
	}
	void mdf(int x, int v) {
		while (x <= n)	
			t[x] += v, x += lowbit(x);
	}
	int qry(int x) {
		int ans = 0;
		while (x > 0)
			ans += t[x], x -= lowbit(x);
		return ans;
	}
} bit;

struct Seg {
	int r, id;
	Seg (int _r = 0, int _id = 0) :
		r(_r), id(_id) {}
};
bool operator<(Seg u, Seg v) {
	return u.r < v.r;
} 

set<Seg> seg[N];//按照 l 储存，r从小到大 

bool vld[N] = {false};//vld[i] 表示 build 时 i 要不要加入 

struct Value {
	int id, mxr;
	Pair mx;
	Value (int _id = 0, int _mxr = ninf, Pair _mx = Pair()) :
		id(_id), mxr(_mxr), mx(_mx) {}
};
Value operator+(Value x, Value y) {
	x.mxr = max(x.mxr, y.mxr);
	x.mx = max(x.mx, y.mx);
	return x;
}
void operator*=(Value &x, int y) {
	x.mx.x += y;
}
struct SegTree1 { 
	Value val[N << 2];
	int tag[N << 2] = {0};
	#define ls (x << 1)
	#define rs (x << 1 | 1)
	#define mid ((lx + rx) >> 1)
	void pushup(int x) {
		val[x] = val[ls] + val[rs];
	}
	void pushdown(int x) {
		if (tag[x] == 0)	
			return;
		val[ls] *= tag[x], val[rs] *= tag[x];
		tag[ls] += tag[x], tag[rs] += tag[x];
		tag[x] = 0;
	}
	void build(int x, int lx, int rx) {
		if (lx + 1 == rx) {
			if (vld[lx]) {
				Seg tmp = *seg[lx].rbegin();
				val[x] = Value(tmp.id, tmp.r, Pair(tmp.r - lx + 1, lx));//初始全是 1 
				seg[lx].erase(tmp);
			}
			return;
		}
		build(ls, lx, mid), build(rs, mid, rx);
		pushup(x); 
	}
	void upd(int x, int lx, int rx, int l, int r, int v) {
		if (rx <= l || r <= lx)	
			return;
		if (l <= lx && rx <= r) {
			val[x] *= v;
			tag[x] += v;
			return;
		}
		pushdown(x);
		upd(ls, lx, mid, l, r, v), upd(rs, mid, rx, l, r, v);
		pushup(x);
	}
	void mdf(int x, int lx, int rx, int pos, Value v) {
		if (lx + 1 == rx) {
			val[x] = v;
			return;
		}
		pushdown(x);
		(pos < mid) ? mdf(ls, lx, mid, pos, v) : mdf(rs, mid, rx, pos, v);
		pushup(x);
	}
	int fnd(int x, int lx, int rx, int R) {//找到第一一个 >= R 的位置，进入之前先判断 
		if (lx + 1 == rx)
			return (val[x].mxr >= R) ? lx : n + 1;
		pushdown(x);
		if (val[ls].mxr >= R)
			return fnd(ls, lx, mid, R);
		return fnd(rs, mid, rx, R);
	}
	int fndL(int x, int lx, int rx, int pos) {//找到 < pos 且存在值的最后位置 
		if (rx <= pos) {
			if (val[x].mxr == ninf)
				return 0;
			if (lx + 1 == rx)	
				return lx;
		}
		pushdown(x);
		if (mid < pos) {
			int res = fndL(rs, rx, mid, pos);
			if (res != -1)
				return res;
		}
		return fndL(ls, lx, mid, pos);
	}
	Value qry(int x, int lx, int rx, int pos) {
		if (lx + 1 == rx)
			return val[x];
		pushdown(x);
		return (pos < mid) ? qry(ls, lx, mid, pos) : qry(rs, mid, rx, pos);
	}
	void del(int pos) {
		//删去 pos 上的数
		int l = fnd(1, 1, n + 1, pos);
		if (l <= pos)
			upd(1, 1, n + 1, l, pos + 1, -1); 
	} 
	SegTree1 () {}
	#undef ls
	#undef rs
	#undef mid 
} st1;

struct SegTree2 {
	Seg val[N << 2];
	#define ls (x << 1)
	#define rs (x << 1 | 1)
	#define mid ((lx + rx) >> 1)
	void pushup(int x) {
		val[x] = max(val[ls], val[rs]);
	}
	void build(int x, int lx, int rx) {
		if (lx + 1 == rx) {
			if (seg[lx].size())
				val[x] = *seg[lx].rbegin();
	//		cout << "Sgt2 " << lx << " " << val[lx].r << " " << val[lx].id << endl;
			return;
		}
		build(ls, lx, mid), build(rs, mid, rx);
		pushup(x);
	}
	void mdf(int x, int lx, int rx, int pos, Seg v) {
		if (lx + 1 == rx) {
			val[x] = v;
			return;
		}
		(pos < mid) ? mdf(ls, lx, mid, pos, v) : mdf(rs, mid, rx, pos, v);
		pushup(x);
	}
	Seg qry(int x, int lx, int rx, int pos) {
		if (lx + 1 == rx)
			return val[x];
		return (pos < mid) ? qry(ls, lx, mid, pos) : qry(rs, mid, rx, pos);
	}
	int fnd(int x, int lx, int rx, int l, int r, int v) {//查找 [l ~ r] 中第一个严格大于 v 的位置 
		if (l >= r)
			return -1;
	//	cout << "in " << lx << " " << rx - 1 << " " << val[x].r << endl;
		if (l <= lx && rx <= r) {
			if (val[x].r <= v)//这段区间不存在 
				return -1;
			if (lx + 1 == rx)
				return lx;
		}
		//否则继续查找
		if (l < mid) {
			int res = fnd(ls, lx, mid, l, r, v);
			if (res != -1)
				return res;
		}
		return fnd(rs, mid, rx, l, r, v);
	}
	SegTree2 () {}
	#undef ls
	#undef rs
	#undef mid
} st2;

vector<int> element[N];
int ans[N] = {0};

void upd(int pos, int v) {//当前 sgt1 中的这条线段可行 
	Value tmp = st1.qry(1, 1, n + 1, pos);
	ans[tmp.id] = v;
	
	//cout << "id: " << tmp.id << " " << tmp.mxr << " pos: " << pos << " " << v << " mx: " << tmp.mx.x << endl;
	
	st1.mdf(1, 1, n + 1, pos, Value());//清空 
	
	//找到两侧的第一条线段
	int L = st1.fndL(1, 1, n + 1, pos);
	int R = st1.fnd(1, 1, n + 1, tmp.mxr);
	int rmx = (L == 0 ? 0 : st1.qry(1, 1, n + 1, L).mxr);
//	cout << "L: " << L << " R: " << R << " rmx: " << rmx << endl;
	//[L + 1, R - 1] 这些位置的所有开始二分
	int npos = st2.fnd(1, 1, n + 1, L + 1, R, rmx);
	while (npos != -1) {
		//将 npos 加入 sgt1
//		cout << "add " << npos << endl;
		Seg nres = st2.qry(1, 1, n + 1, npos);
		int val = bit.qry(nres.r) - bit.qry(npos - 1);
		st1.mdf(1, 1, n + 1, npos, Value(nres.id, nres.r, Pair(val, npos)));
		//将 npos 从 sgt2 中删去
		st2.mdf(1, 1, n + 1, npos, Seg());
		seg[npos].erase(nres);
		if (seg[npos].size()) {
			st2.mdf(1, 1, n + 1, npos, *seg[npos].rbegin());
		} 
		rmx = nres.r;
		npos = st2.fnd(1, 1, n + 1, npos + 1, R, rmx);
	} 
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]), a[i] = min(a[i], n);
		element[a[i]].push_back(i);
	}
	for (int i = 1, l, r; i <= m; i++) {
		scanf("%d%d", &l, &r);
		seg[l].insert(Seg(r, i));
	}
	int rmx = 0;
	for (int i = 1; i <= n; i++) {
		if (seg[i].size()) {
			if ((*seg[i].rbegin()).r > rmx) 
				vld[i] = true, rmx = (*seg[i].rbegin()).r;//, cout << i << " " << rmx << endl;
		}
	}
	bit.init();
	for (int i = 1; i <= n; i++)
		bit.mdf(i, 1);
//	cout << "After building bit " << endl;
	st1.build(1, 1, n + 1);
//	cout << "sgt1" << endl;
	st2.build(1, 1, n + 1); 
//	cout << "scanning" << endl;
	//开始扫描值域
	for (int i = n; i >= 0; i--) {
		//先将 i 全部删去 
		for (auto j: element[i]) {
			st1.del(j);
			bit.mdf(j, -1);
		}
		//然后将所有 >= i 的找出来并更新答案
		while (st1.val[1].mx.x >= i) {
			upd(st1.val[1].mx.y, i);
		}
	} 
	for (int i = 1; i <= m; i++)
		printf("%d\n", ans[i]);
	return 0;
}