#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cctype>
#include <ctime>
#define LL long long
int read() {
	int x=0,minus=0; char ch;
	while (!isdigit(ch=getchar())) minus|=(ch=='-');
	while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
	return minus?-x:x;
}
const int N=5e5+10,INF=1e6;
int n,m,a[N],id[N],bl[N];
bool sz[N<<2];
int maxn[N<<2],minn[N<<2];
LL cnt[N<<2];
int max(int x,int y) {return x>y?x:y;}
int min(int x,int y) {return x<y?x:y;}
int F(int x) {return x<0?-x:x;}
void push_up(int k) {
	const int ls=k<<1,rs=k<<1|1;
	sz[k]=sz[ls]|sz[rs];
	cnt[k]=cnt[ls]+cnt[rs];
	if (sz[ls]&sz[rs]) {
		cnt[k]+=F(id[minn[rs]]-id[maxn[ls]]);
		maxn[k]=max(maxn[ls],maxn[rs]);
		minn[k]=min(minn[ls],minn[rs]);
	} else {
		if (sz[ls]) maxn[k]=maxn[ls],minn[k]=minn[ls];
		else if (sz[rs]) maxn[k]=maxn[rs],minn[k]=minn[rs]; 
		else maxn[k]=-INF,minn[k]=INF;
	}
}
void build(int k,int l,int r) {
	if (l==r) {
		sz[k]=false; cnt[k]=0;
		maxn[k]=r; minn[k]=l;
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid); build(k<<1|1,mid+1,r);
	push_up(k);
}
void update(int k,int l,int r,int x) {
	if (l==r) {sz[k]^=1; return;}
	int mid=(l+r)>>1;
	if (x<=mid) update(k<<1,l,mid,x);
	else update(k<<1|1,mid+1,r,x);
	push_up(k);
}
LL ans[N];
int c[N];
struct node{int l,r,id;}mo[N],pl[N],pr[N],p1[N],p2[N];
bool cmp1(node x,node y) {return x.l<y.l;}
bool cmp2(node x,node y) {return x.r>y.r;}
void solve(int l,int r,int x,int y) {
	if (l>=r||x>y) return; int mid=(l+r)>>1;
	for (int i=l;i<=r;++i) c[i]=a[i];
	std::nth_element(c+l,c+mid,c+r+1);
	int pos=mid+1;
	for (int i=mid+1;i<=r;++i) if (c[i]<c[pos]) pos=i;
	int tmp=F(id[c[mid]]-id[c[pos]]),xx=x-1,yy=y+1,tp=0;
	for (int i=x;i<=y;++i) {
		if (mo[i].r<=mid) pl[++xx]=mo[i];
		else if (mo[i].l>mid) pr[++yy]=mo[i];
		else {
			ans[mo[i].id]+=tmp;
			p1[++tp]=mo[i]; p2[tp]=mo[i];
		}
	}
	int t1=tp,t2=tp;
	std::sort(p1+1,p1+1+tp,cmp1);
	for (int i=mid;i>=l;--i) {
		update(1,1,n,a[i]);
		while (t1&&p1[t1].l==i) ans[p1[t1].id]+=cnt[1],--t1;
	}
	for (int i=mid;i>=l;--i) update(1,1,n,a[i]);
	std::sort(p2+1,p2+1+tp,cmp2);
	for (int i=mid+1;i<=r;++i) {
		update(1,1,n,a[i]);
		while (t2&&p2[t2].r==i) ans[p2[t2].id]+=cnt[1],--t2;
	}
	for (int i=mid+1;i<=r;++i) update(1,1,n,a[i]);
	for (int i=x;i<=xx;++i) mo[i]=pl[i]; 
	for (int i=yy;i<=y;++i) mo[i]=pr[i];
	solve(l,mid,x,xx); solve(mid+1,r,yy,y);
}
signed main() {
	n=read(); m=read(); int LN=sqrt(n); bool pf=true;
	for (int i=1;i<=n;++i) {
		a[i]=read(); id[a[i]]=i;
		if (F(a[i]-i)>10) pf=false;
	}
	for (int i=1;i<=n;++i) bl[i]=(i/LN)+1;
	for (int i=1;i<=m;++i) {
		int x=read(),y=read();
		mo[i]=(node){x,y,i};
	}
	solve(1,n,1,m);
	for (int i=1;i<=m;++i) printf("%lld\n",ans[i]);
	return 0;
}