#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using u64=unsigned long long;
using u32=unsigned;
using i128=__int128;
using lf=long double;
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define F(i,l,r) for(int i=l,R_F=r;i<=R_F;++i)
#define G(i,r,l) for(int i=r,L_F=l;i>=L_F;--i)
#define il inline
#define ct const
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#define CUT dbg("**********\n")
//ct int INF=1.02e9;
ct ll INF=4e18L;
ct lf PI=acos(-1L),EPS=1e-9L;
il int dcmp(lf x){return fabs(x)<=EPS?0:(x<0?-1:1);}
template<class T>
il void tomx(T&x,T y){x<y?x=y,0:0;}
template<class T>
il void tomn(T&x,T y){y<x?x=y,0:0;}
ct ll P=998244353;
il ll qpow(ll x,ll y){
	ll r=1;for(;y;y>>=1,x=x*x%P)y&1?(r=r*x%P):0;return r;
}
il ll inv(ll x){return qpow(x,P-2);}
il void add(int&x,int y){x+=y,x-=(x>=P)*P;}

ct int N=1000500;
class BIT{
	int d[N];
public:
	void init(){
//		dbg("BIT.init()\n");
		memset(d,0,sizeof(d));
	}
	int qry(int i){
//		dbg("BIT.qry(%d)=",i);
		int x=0;for(;i;i-=(i&-i))x+=d[i];
//		dbg("%d\n",x);
		return x;
	}
	int kth(int k){
		int i=0;
		G(j,20,0){
			int x=i+(1<<j);
			if(x<N&&k>d[x])
				i=x,k-=d[x];
		}return i+1;
	}
//	void wt(){
//		F(i,1,10)dbg("%d ",qry(i));
//		dbg("\n");
//	}
	void upd(int i,int x){
//		dbg("BIT.upd(%d,%d)\n",i,x);
		for(;i<N;i+=(i&-i))d[i]+=x;
//		wt();
	}
}sol;
int n,q,a[N],pre[N],nxt[N],ans[N],top,st[N];
vector<int>idx[N];
struct Pnt{int r,x;};vector<Pnt>pnt[N];
struct Qry{int r,i;};vector<Qry>qr[N];
int main(){
#ifdef LOCAL
	freopen("QOJ7771.in","r",stdin);
//	freopen(".out","w",stdout);
#endif
	scanf("%d%d",&n,&q);
	F(i,1,n)scanf("%d",a+i),idx[a[i]].pb(i);
	a[0]=a[n+1]=0,st[top=1]=0;
	F(i,1,n){
		while(a[st[top]]>=a[i])--top;
		pre[i]=st[top],st[++top]=i;
	}st[top=1]=n+1;
	G(i,n,1){
		while(a[st[top]]>=a[i])--top;
		nxt[i]=st[top],st[++top]=i;
	}sol.init();
	
//	CUT;
//	F(i,1,n)dbg("%d ",pre[i]);
//	dbg("\n");
//	F(i,1,n)dbg("%d ",nxt[i]);
//	dbg("\n");
//	CUT;
	
	G(x,n,1){
		F(pos,0,(int)idx[x].size()-1){
			int i=idx[x][pos],l=pre[i],r=nxt[i];
			pnt[i].pb(Pnt{i,1});
//			dbg("x=%d,Pnt=%d %d %d\n",x,i,i,1);
			pnt[l].pb(Pnt{i,-1});
//			dbg("x=%d,Pnt=%d %d %d\n",x,l,i,-1);
			int cnt=lower_bound(idx[x].begin(),idx[x].end(),r)-idx[x].begin()-pos;
			int j=sol.kth(sol.qry(r)+cnt);
			pnt[i].pb(Pnt{j,-1});
//			dbg("x=%d,Pnt=%d %d %d\n",x,i,j,-1);
		}
		for(int i:idx[x])
			sol.upd(i,1);
	}
	F(i,1,q){
		int l,r;scanf("%d%d",&l,&r);
		qr[l].pb(Qry{r,i}),ans[i]=r-l+1;
	}sol.init();
	G(l,n,1){
		for(Pnt x:pnt[l])
			sol.upd(x.r,x.x);
		for(Qry x:qr[l])
			ans[x.i]-=sol.qry(x.r);
	}
	F(i,1,q)printf("%d\n",ans[i]);
}