#include<bits/stdc++.h>
using namespace std;
int n,m,a[1010000],t[1010000];
struct ed{int l,r,z;};
vector<ed>g[1010000];
int head[1010010],nxt[1001000];
int sta[1010000],top,lc[1010000],rc[1010000],fa[1010000],tr[1010000],ans[1010000];
int F(int x){if(x==fa[x])return x;return fa[x]=F(fa[x]);}
void ag(int xl,int xr,int yl,int yr){g[xl].push_back((ed){yl,yr,1}),g[xr+1].push_back((ed){yl,yr,-1});}
void ad(int x,int z){for(;x<=n;x+=(x&-x))tr[x]+=z;}
int ask(int x){int s=0;for(;x;x-=(x&-x))s+=tr[x];return s;}
int main(){
	//freopen("data3.in","r",stdin);
	//freopen("data.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]),a[i]=n+1-a[i];
	for(int i=1;i<=n;i++){
		nxt[i]=head[a[i]],head[a[i]]=i;
		while(top&&a[sta[top]]<=a[i])top--;
		lc[i]=sta[top],sta[++top]=i;
	}
	sta[0]=n+1;top=0;
	for(int i=n;i;i--){
		while(top&&a[sta[top]]<=a[i])top--;
		rc[i]=sta[top],sta[++top]=i;
	}
	for(int i=1;i<=n+1;i++)fa[i]=i;
	for(int i=n;i;i--){
		for(int j=head[i];j;j=nxt[j])fa[j]=F(j+1);
		int p0=-1,tt=-1;
		for(int j=head[i];j;j=nxt[j]){
			if(rc[j]!=tt)p0=F(rc[j]);
			else p0=((p0<=n)?F(p0+1):(n+1));
			ag(lc[j]+1,j,j,p0-1);
			tt=rc[j];
		}
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
	for(int i=1,l,r;i<=m;i++)scanf("%d%d",&l,&r),ans[i]=r-l+1,g[l].push_back((ed){r,i,0});
	for(int i=1;i<=n;i++){
		for(ed t:g[i])if(t.z)ad(t.l,t.z),ad(t.r+1,-t.z);
		for(ed t:g[i])if(!t.z)ans[t.r]-=ask(t.l);
	}
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
	return 0;
}

answer.code: In function ‘int main()’:
answer.code:39:51: error: ‘s’ was not declared in this scope
   39 |         for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
      |                                                   ^
answer.code:15:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   15 |         scanf("%d%d",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~
answer.code:17:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   17 |         scanf("%d",&a[i]),a[i]=n+1-a[i];
      |         ~~~~~^~~~~~~~~~~~
answer.code:40:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   40 |         for(int i=1,l,r;i<=m;i++)scanf("%d%d",&l,&r),ans[i]=r-l+1,g[l].push_back((ed){r,i,0});
      |                                  ~~~~~^~~~~~~~~~~~~~