#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int N = 5e5+5;
int a[N];
struct que{int l,r,id;}q[N];
vector < int > ve[N];

bool cmp(que a,que b)
{return a.l == b.l ? a.r > b.r : a.l < b.l;}

struct tree{int l,r,mx,laz;}tr[N<<2],t1[N<<2];

void build(int l,int r,int i)
{
	tr[i].l = l,tr[i].r = r;
	if(l == r) return (void)(tr[i].mx = q[l].r);
	int mid = (l+r)>>1;
	build(l,mid,i<<1),build(mid+1,r,i<<1|1);
	tr[i].mx = max(tr[i<<1].mx,tr[i<<1|1].mx);
}

void M(int p,int i)
{
	if(tr[i].l == tr[i].r) return (void)(tr[i].mx = -1e9);
	if(p <= tr[i<<1].r) M(p,i<<1);
	else M(p,i<<1|1);
	tr[i].mx = max(tr[i<<1].mx,tr[i<<1|1].mx);
}

int Q(int l,int r,int k,int i)
{
	if(tr[i].l > r || tr[i].r < l) return 0;
	if(tr[i].l == tr[i].r) return tr[i].l;
	if(tr[i<<1].mx > k) return Q(l,r,k,i<<1);
	if(tr[i<<1|1].mx > k) return Q(l,r,k,i<<1|1);
	return 0;
}

void B(int l,int r,int i)
{
	t1[i].l = l,t1[i].r = r;
	if(l == r) return ;
	int mid = (l+r)>>1;
	B(l,mid,i<<1),B(mid+1,r,i<<1|1);
}

void down(int i)
{
	t1[i<<1].mx += t1[i].laz,t1[i<<1|1].mx += t1[i].laz;
	t1[i<<1].laz += t1[i].laz,t1[i<<1|1].laz += t1[i].laz;
	t1[i].laz = 0;
}

void M1(int l,int r,int i)
{
	if(t1[i].l >= l && t1[i].r <= r)
		return (void)(t1[i].mx--,t1[i].laz--);
	if(t1[i].laz) down(i);
	if(t1[i<<1].r >= l) M1(l,r,i<<1);
	if(t1[i<<1|1].l <= r) M1(l,r,i<<1|1);
	t1[i].mx = max(t1[i<<1].mx,t1[i<<1|1].mx);
}

void M2(int p,int k,int i)
{
	if(t1[i].l == t1[i].r)
		return (void)(t1[i].mx = k);
	if(t1[i].laz) down(i);
	if(p <= tr[i<<1].r) M2(p,k,i<<1);
	else M2(p,k,i<<1|1);
	t1[i].mx = max(t1[i<<1].mx,t1[i<<1|1].mx);
}

vector < int > v,tmp;

int c[N],ans[N],n,t;

void A(int i,int k)
{while(i <= n) c[i] += k,i += i&-i;}

int Q1(int i)
{
	int res = 0;
	while(i) res += c[i],i -= i&-i;
	return res;
}

int getl(int k)
{
	int l = 0,r = v.size()-1;
	while(l < r)
	{
		int mid = (l+r)>>1;
		if(q[v[mid]].r < k) l = mid+1;
		else r = mid;
	}
	while (l <= v.size() && q[v[l]].r < k) ++l;
	return l;
}

int getr(int k)
{
	int l = 0,r = v.size()-1;
	while(l < r)
	{
		int mid = (l+r+1)>>1;
		if(q[v[mid]].l > k) r = mid-1;
		else l = mid;
	}
	while (l >= 0 && q[v[l]].l > k) --l;
	return l;
}

void D(int k,int i)
{
	if(t1[i].l == t1[i].r)
	{
		t1[i].mx = -1e9;ans[q[t1[i].l].id] = k;
		int r = upper_bound(begin(v),end(v),t1[i].l)-begin(v),l = lower_bound(begin(v),end(v),t1[i].l)-begin(v)-1;
		l = l < 0 ? 0 : v[l];r = (r == v.size()) ? t : v[r];
		int las = q[l].r;
		while(1)
		{
			int id = Q(l+1,r,las,1);
			if(!id) break;
			M(id,1);
			int s = Q1(q[id].r)-Q1(q[id].l-1);
			if(s >= k) {ans[q[id].id] = k;continue;}
			M2(id,s,1);l = id,las = q[id].r;tmp.pb(id);
		}
		v.erase(lower_bound(begin(v),end(v),t1[i].l));
		for (int j : tmp) v.insert(lower_bound(begin(v),end(v),j),j);
		tmp.clear();
		return ;
	}
	if(t1[i].laz) down(i);
	if(t1[i<<1].mx >= k) D(k,i<<1);
	if(t1[i<<1|1].mx >= k) D(k,i<<1|1);
	t1[i].mx = max(t1[i<<1].mx,t1[i<<1|1].mx);
}

int main()
{
	// freopen("set.in","r",stdin);
	// freopen("set.out","w",stdout);
	// ios::sync_with_stdio(0);
	cin >> n >> t;
	for (int i = 1;i <= n;i++)
		cin >> a[i],ve[a[i]+1].pb(i),A(i,1);
	for (int i = 1;i <= t;i++)
		cin >> q[i].l >> q[i].r,q[i].id = i;
	sort(q+1,q+t+1,cmp);
	build(1,t,1);B(1,t,1);
	int k = n,las = 0,l = 0;
	while(1)
	{
		int id = Q(l+1,t,las,1);
		if(!id) break;
		M(id,1);
		int s = Q1(q[id].r)-Q1(q[id].l-1);
		if(s >= k){ans[q[id].id] = k;continue;}
		M2(id,s,1);l = id,las = q[id].r;v.pb(id);
	}
	while(k)
	{ 
		for (auto i : ve[k])
		{
			int L = getl(i),R = getr(i);
			if (L >= 0 && L < v.size() && R >= 0 && R < v.size())
				M1(v[L],v[R],1);
			A(i,-1);
		}
		k--;
		if(!k) break;
		D(k,1);
	}
	for (int i = 1;i <= t;i++) cout << ans[i] << '\n';
	return 0;
}