#include<bits/stdc++.h>
#define LC x<<1
#define RC x<<1|1
#define il inline
#define inf 1e9
#define ll int
using namespace std;
ll n,m,a[500050],pos[500050];
ll ans[1010][1010],tree[2000020];
ll c,len,blg[500050],lhakioi=0;
struct node{
	ll l,r,id,lmhakioi;
}q[500050];
il void sub1(){
	for(ll i=1;i<=m;i++){
		ll ql,qr,lst=0,ans=0;
		scanf("%d %d",&ql,&qr);
		for(ll j=1;j<=n;j++) pos[j]=0;
		for(ll j=ql;j<=qr;j++) pos[a[j]]=j;
		for(ll i=1;i<=n;i++){
			if(pos[i]){
				if(lst) ans+=abs(pos[i]-pos[lst]);
				lst=i;
			}
		}
		printf("%d\n",ans);
	}
}
il void pushup(ll x){
	tree[x]=tree[LC]+tree[RC];
}
void mdf(ll x,ll l,ll r,ll pos,ll v){
	if(l==r){
		tree[x]+=v;
		return;
	}
	ll mid=(l+r)>>1;
	if(pos<=mid) mdf(LC,l,mid,pos,v);
	else mdf(RC,mid+1,r,pos,v);
	pushup(x);
}
ll query(ll x,ll l,ll r,ll ql,ll qr){
	if(ql>qr) return 0;
	if(ql<=l&&r<=qr) return tree[x];
	ll mid=(l+r)>>1,res=0;
	if(ql<=mid) res+=query(LC,l,mid,ql,qr);
	if(mid<qr) res+=query(RC,mid+1,r,ql,qr);
	return res;
}
il ll get_pre(ll x){
	ll l=1,r=x-1,tmp=query(1,1,n,l,r);
	if(!tmp) return -inf;
	while(l<r){
		ll mid=(l+r+1)>>1;
		tmp=query(1,1,n,mid,r);
		if(tmp) l=mid;
		else r=mid-1;
	}
	return l;
}
il ll get_nxt(ll x){
	ll l=x+1,r=n,tmp=query(1,1,n,l,r);
	if(!tmp) return inf;
	while(l<r){
		ll mid=(l+r)>>1;
		tmp=query(1,1,n,l,mid);
		if(tmp) r=mid;
		else l=mid+1;
	}
	return l;
}
il void sub6(){
	for(ll i=1;i<=n;i++){
		ll now=0;
		for(ll j=i;j<=n;j++){
			pos[a[j]]=j;
			mdf(1,1,n,a[j],1);
			ll pree=get_pre(a[j]),nxtt=get_nxt(a[j]);
			if(pree!=-inf) now+=abs(pos[pree]-j);
			if(nxtt!=inf) now+=abs(pos[nxtt]-j);
			if(pree!=-inf&&nxtt!=inf) now-=abs(pos[pree]-pos[nxtt]);
			ans[i][j]=now;
		}
		for(ll j=i;j<=n;j++){
			pos[a[j]]=0;
			mdf(1,1,n,a[j],-1);
		}
	}
	for(ll i=1;i<=m;i++){
		ll ql,qr;
		scanf("%d %d",&ql,&qr);
		printf("%d\n",ans[ql][qr]);
	}
}
il bool cmp(node x,node y){
	if(blg[x.l]==blg[y.l]){
		if(blg[x.l]&1) return x.r<y.r;
		else return x.r>y.r;
	}
	return blg[x.l]<blg[y.l];
}
il bool ztcakioi(node x,node y){
	return x.id<y.id;
}
il void ins(ll p){
	pos[a[p]]=p;
	mdf(1,1,n,a[p],1);
	ll pree=get_pre(a[p]),nxtt=get_nxt(a[p]);
	if(pree!=-inf) lhakioi+=abs(pos[pree]-p);
	if(nxtt!=inf) lhakioi+=abs(pos[nxtt]-p);
	if(pree!=-inf&&nxtt!=inf) lhakioi-=abs(pos[pree]-pos[nxtt]);
}
il void del(ll p){
	pos[a[p]]=0;
	mdf(1,1,n,a[p],-1);
	ll pree=get_pre(a[p]),nxtt=get_nxt(a[p]);
	if(pree!=-inf) lhakioi-=abs(pos[pree]-p);
	if(nxtt!=inf) lhakioi-=abs(pos[nxtt]-p);
	if(pree!=-inf&&nxtt!=inf) lhakioi+=abs(pos[pree]-pos[nxtt]);
}
il void sub(){
	len=sqrt(n);
	if(n%len==0) c=n/len;
	else c=n/len+1;
	for(int i=1;i<=c;i++){
		for(int j=1;j<=len;j++){
			ll tmp=(i-1)*len+j;
			if(tmp>n) break;
			blg[tmp]=i;
		}
	}
	for(ll i=1;i<=m;i++){
		scanf("%d %d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	ll l=1,r=0;
	for(ll i=1;i<=m;i++){
		while(r<q[i].r){
			r++;
			ins(r);
		}
		while(l>q[i].l){
			l--;
			ins(l);
		}
		while(r>q[i].r){
			del(r);
			r--;
		}
		while(l<q[i].l){
			del(l);
			l++;
		}
		q[i].lmhakioi=lhakioi;
	}
	sort(q+1,q+m+1,ztcakioi);
	for(ll i=1;i<=m;i++) printf("%d\n",q[i].lmhakioi);
}
ll main(){
//	freopen("rrads.in","r",stdin);
//	freopen("rrads.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(ll i=1;i<=n;i++) scanf("%d",&a[i]);
	if(n<=1000&&m<=1000) sub1();
	else if(m==n*(n-1)/2) sub6();
	else sub();
	return 0;
}