#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++
#define putchar(x) (p3 - obuf < 1000000) ? (*p3++ = x) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3++ = x)
using namespace std;
static char buf[29999999], *p1 = buf, *p2 = buf, obuf[29999999], *p3 = obuf;
template <typename item>
inline void read (register item &x) {
    x = 0;
	register char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
}
static char cc[15];
template <typename item>
inline void print (register item x) {
	register int len = 0;
	do cc[len++] = x % 10 + '0', x /= 10; while (x);
	while (len--) putchar(cc[len]);
}
int a[1000005],n,q;
int c[1000005],Ans[1000005],qr[1000005];
vector<int>que[1000050],vec[1000500];
vector<pii>ins[1000005];
void add(int p,int o){
	for(int i=p;i<=n;i+=(i&-i))c[i]+=o;
}
int qry(int p){
	int ans=0;
	for(int i=p;i;i&=(i-1))ans+=c[i];
	return ans;
}
int rg[1000005],lf[1000005],stk[1000005],tail;
int pos[1000005],tot;
set<int>val;
int Nxt[1000005];
int nxt(int x){
	set<int>::iterator it=val.upper_bound(x);
	return (*it);
}
int main(){
	read(n),read(q);
	for(int i=1;i<=n;++i)read(a[i]),vec[a[i]].pb(i);stk[0]=n+1;
	for(int i=n;i>=1;--i){
		while(tail&&a[stk[tail]]>=a[i])--tail;
		rg[i]=stk[tail],stk[++tail]=i;
	}tail=0,stk[0]=0;
	for(int i=1;i<=n;++i){
		while(tail&&a[stk[tail]]>=a[i])--tail;
		lf[i]=stk[tail],stk[++tail]=i;
	}
	for(int i=1;i<=q;++i){
		int x;read(x),read(qr[i]);
		que[x].push_back(i);
	}
	val.insert(n+1);
	val.insert(n+2);
	Nxt[n+1]=n+2;
	for(int V=n;V>=1;--V){
		if(!vec[V].size())continue;tot=0;
		for(auto v:vec[V])pos[++tot]=v,ins[1].pb(mp(v,1));
		pos[tot+1]=n+1;
		for(int l=1;l<=tot;){
			int r=l;while(r<tot&&rg[pos[r+1]]==rg[pos[r]])++r;tail=0;
			for(int i=nxt(rg[pos[r]]),c=1;i<=n&&c<=r-l+1;i=Nxt[i],++c)stk[++tail]=i;
			int lst=lf[pos[l]]+1;
			for(int i=l;i<=r;++i)ins[lst].pb(mp(pos[i],-1));
			for(int i=1;i<=tail;++i)ins[lst].pb(mp(stk[i],1));
			for(int i=l;i<=r;++i){
				int sz=r-i+1;
				while(tail>sz)ins[lst].pb(mp(stk[tail--],-1));
				lst=pos[i]+1;
			}
			while(tail)ins[lst].pb(mp(stk[tail--],-1));
			l=r+1;
		}
		for(auto v:vec[V]){
			set<int>::iterator it=val.lower_bound(v),it1=it;
			if(it1==val.begin())Nxt[v]=(*it);
			else Nxt[*(--it1)]=v,Nxt[v]=(*it);
			val.insert(v);
		}
	}
	for(int i=1;i<=n;++i){
		for(auto v:ins[i])add(v.fi,v.se);
		for(auto v:que[i])Ans[v]=qry(qr[v]);
	}
	for(int i=1;i<=q;++i)print(Ans[i]),putchar('\n');
	fwrite(obuf, p3 - obuf, 1, stdout);
	return 0;
}