#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=200005;
struct qs
{
	int id,l,r;
}q[N];
int n,m,a[N],ans[N],cnt[N],res,len,st[N][20],t[N],pre[N],nxt[N],l,r;
inline bool cmp1(qs a,qs b)
{
	if(a.l/len==b.l/len) return a.r<b.r;
	return a.l<b.l;
}
int query(int l,int r)
{
	int k=0;
	while((1<<(k+1))<r-l+1) ++k;
	return min(st[l][k],st[r-(1<<k)+1][k]);
}
void add(int i,int k)
{
	int j;
	if(k==1) j=pre[i];
	else if(k==0) j=nxt[i];
	if(!j||j<l||j>r)
	{
		++res;
		return ;
	}
	int x=query(min(i,j),max(i,j));
	if(x<a[i]) ++res;
}
void del(int i,int k)
{
	int j;
	if(k==1) j=pre[i];
	else if(k==0) j=nxt[i];
	if(!j||j<l||j>r)
	{
		--res;
		return ;
	}
	int x=query(min(i,j),max(i,j));
	if(x<a[i]) --res;
}
int main()
{
	freopen("usaco_21Feb_dry.in","r",stdin);
	freopen("usaco_21Feb_dry.out","w",stdout);
	scanf("%d%d",&n,&m);
	len=sqrt(n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		st[i][0]=a[i];
		pre[i]=t[a[i]];
		t[a[i]]=i;
	}
	for(int i=1;i<=n;++i)
		if(pre[i])
			nxt[pre[i]]=i;
	for(int i=1;i<=m;++i) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
	for(int i=1;i<=18;++i)
		for(int j=1;j+(1<<i)-1<=n;++j)
			st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
	sort(q+1,q+1+m,cmp1); 
	l=1,r=0;
	for(int i=1;i<=m;++i)
	{
		while(r<q[i].r) add(++r,1);
		while(r>q[i].r) del(r--,1);
		while(l<q[i].l) del(l++,0);
		while(l>q[i].l) add(--l,0);
		ans[q[i].id]=res;
	}
	for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
	return 0;
}