#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,a[501000];
int cp[500010];
int id[1111][1111];
ll anss[501000];
set<int>s;
void pts20_all(){
	for(int i=1,l,r;i<=m;i++)
		scanf("%d%d",&l,&r),id[l][r]=i;
	for(int i=1;i<=n;i++){
		s.clear();
		ll ans=0;
		for(int j=i;j<=n;j++){
			set<int>::iterator it=s.lower_bound(a[j]);
			int pre=-1,nxt=-1;
			if(it!=s.end())nxt=*it;
			if(it!=s.begin())pre=*(--it);
			if(nxt!=-1&&pre!=-1)ans-=abs(cp[nxt]-cp[pre]);
			if(nxt!=-1)ans+=abs(j-cp[nxt]);
			if(pre!=-1)ans+=abs(j-cp[pre]);
			s.insert(a[j]);
			anss[id[i][j]]=ans;
		}
	}
	for(int i=1;i<=m;i++)printf("%lld\n",anss[i]);
}
ll sg[500100],now;
int pr[500100],nx[500010],L,R;
int top,rp[500100],xn[500100],po[500100];
void del(int x){
	int A=pr[x],B=nx[x];
	po[++top]=x,rp[top]=A,xn[top]=B;
	if(A>=L)now-=abs(cp[A]-cp[x]);
	if(B<=R)now-=abs(cp[B]-cp[x]);
	if(L<=A&&B<=R)now+=abs(cp[A]-cp[B]);
	pr[B]=A,nx[A]=B;
}
void ins(int x,int A,int B){
	if(A>=L)now+=abs(cp[A]-cp[x]);
	if(B<=R)now+=abs(cp[B]-cp[x]);
	if(L<=A&&B<=R)now-=abs(cp[A]-cp[B]);
	pr[x]=A,nx[x]=B,pr[B]=x,nx[A]=x;
}
void pts20_abs10(){
	for(int i=2;i<=n;i++)sg[i]=sg[i-1]+abs(cp[i]-cp[i-1]);
	for(int i=1;i<=n;i++)pr[i]=i-1,nx[i]=i+1;
	nx[0]=1,pr[n+1]=n;
	for(int i=1,l,r;i<=m;i++){
		cin>>l>>r;
		R=min(r+10,n),L=max(1,l-10);
		now=sg[R]-sg[L];
		for(int j=L;j<l;j++)del(a[j]);
		for(int j=r+1;j<=R;j++)del(a[j]);
		printf("%lld\n",now);
		while(top)ins(po[top],rp[top],xn[top]),top--;
	}
}
int S,Pr[500010],Nx[500100],l[501000],r[500100];
vector<int>g[810][810]; 
void fenkuai(){
	nx[0]=n+1,pr[n+1]=0;L=1,R=n;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&l[i],&r[i]);
		g[(l[i]-1)/S+1][(r[i]-1)/S+1].push_back(i);
	}
	int t=(n-1)/S+1;
	for(int i=1;i<=t;i++){
		int o=(i-1)*S+1;
		now=0;
		int np=i,pp=0;
		for(int j=1;j<=n;j++)if(cp[j]>=o)Pr[j]=pp,pp=j;
		Pr[n+1]=pp;pp=n+1;
		for(int j=n;j;j--)if(cp[j]>=o)Nx[j]=pp,pp=j;
		Nx[0]=pp;
		for(int j=n;j>=o;j--)
			Pr[Nx[a[j]]]=Pr[a[j]],Nx[Pr[a[j]]]=Nx[a[j]];
		for(int j=o;j<=n;j++){
			int pre=0,nxt=n+1;
			ins(a[j],Pr[a[j]],Nx[a[j]]);
			if(j==np*S||j==n){
				for(int pp=0;pp<g[i][np].size();pp++){
					int id=g[i][np][pp];
					for(int k=o;k<l[id];k++)del(a[k]);
					for(int k=r[id]+1;k<=j;k++)del(a[k]);
					anss[id]=now;
					while(top)ins(po[top],rp[top],xn[top]),top--;
				}
				np++;
			}
		}
	}
	for(int i=1;i<=m;i++)printf("%lld\n",anss[i]);
}
int main(){
	freopen("rrads.in","r",stdin);
	freopen("rrads.out","w",stdout);
	cin>>n>>m;
	bool fl=1;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),fl&=(abs(a[i]-i)<=10),cp[a[i]]=i;
	if(m==1ll*n*(n-1)/2)pts20_all();
	else if(fl)pts20_abs10();
	else S=sqrt(n),fenkuai();
	return 0;
}