#include <bits/stdc++.h>
using namespace std;
const int N=200000+5;
int n,m,t;
int a[N],ans[N],now=0;
int num[N]={0};
struct sdf{
	int l,r,id;
}q[N];
bool cmp(sdf x,sdf y){
	if (x.l/t!=y.l/t)return x.l<y.l;
	if ((x.l/t)&1)return x.r<y.r;
	else return x.r>y.r;
}
void add(int x,int opt){
	int y;
	if (opt==0)y=a[x+1];
	else y=a[x-1];
	x=a[x];
	if (x>y||!num[x])now++;
	num[x]++;
	return ;
}
void del(int x,int opt){
	int y;
	if (opt==0)y=a[x+1];
	else y=a[x-1];
	x=a[x];
	if (x>y||num[x]==1)now--;
	num[x]--;
	return ;
}
int main(){
	freopen ("usaco_21Feb_dry.in","r",stdin);
	freopen ("usaco_21Feb_dry.out","w",stdout);
	scanf("%d%d",&n,&m);t=sqrt(n);
	for (int i=1;i<=n;i++)scanf("%d",&a[i]);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	int nowl=1,nowr=0;
	for (int i=1;i<=m;i++){
		int l=q[i].l,r=q[i].r;
		while(nowr<r)add(++nowr,1);
		while(nowl>l)add(--nowl,0);
		while(nowl<l)del(nowl++,0);
		while(nowr>r)del(nowr--,1);
		ans[q[i].id]=now;
	}
	for (int i=1;i<=m;i++)printf("%d\n",ans[i]);
	return 0;
}