#include<bits/stdc++.h>
#define fre(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define ll long long
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') { if(c=='-') f=-1;c=getchar(); }
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=getchar();
	return x*f;
}
const int N=2.5e4+5;
int n,m;
int l[N],r[N],pre[N][2],suc[N][2],a[N];
int ans;
void solve(){
	int L=read(),R=read();
	for(int i=L;i<=R;i++){
		for(;l[i]>=L;l[i]--){
			int p=a[l[i]]>a[i];
			if((a[l[i]]>a[pre[i][p]])^p){
				ans-=(i==suc[pre[i][p]][p^1]);
				ans+=(i==suc[l[i]][p^1]);
				pre[i][p]=l[i];
			}
		}
		for(;r[i]<=R;r[i]++){
			int p=a[r[i]]>a[i];
			if((a[r[i]]>a[suc[i][p]])^p){
				ans-=(i==pre[suc[i][p]][p^1]);
				ans+=(i==pre[r[i]][p^1]);
				suc[i][p]=r[i];
			}
		}
	}
	printf("%d\n",ans);
}
int main(){
	n=read(),m=read();
	a[0]=n+1;
	for(int i=1;i<=n;i++){
		a[i]=read();
		l[i]=i-1,r[i]=i+1;
		pre[i][1]=suc[i][1]=0;
		pre[i][0]=suc[i][0]=n+1;
	}
	while(m--) solve();
	return 0;
}