#include<cstdio>
#include<algorithm>
#include<cassert>
#include<ctime>
#include<vector>
#include<random>
std::mt19937 rnd(time(0));
inline int ib(int x){return x>0?x:-x;}
typedef long long lli;
const int N=5e5,B=707;

int n,q,pe[N+5],po[N+5];

lli ans[N+5];

struct QR{
	int w,l,r;
	QR(){}
	QR(int _w,int _l,int _r){w=_w,l=_l,r=_r;}
};
std::vector<QR>qr[B+5];

lli rs;
int pr[N+5],nx[N+5];
bool us[N+5];
inline void init(int l,int r){
	rs=0;
	std::fill(pr,pr+n+2,0),std::fill(nx,nx+n+2,0),std::fill(us,us+n+2,0);
	us[0]=us[n+1]=1;for(int i=l;i<=r;++i)us[pe[i]]=1;
	for(int i=1,u=0;i<=n+1;++i)if(us[i]){
		if(u&&i<=n)rs+=ib(po[i]-po[u]);
		pr[i]=u,nx[u]=i;
		u=i;
	}
}
inline void del(int w){
	int x=pe[w],y=pr[x],z=nx[x],u=po[y],v=po[z];
	if(y)rs-=ib(w-u);
	if(z<=n)rs-=ib(v-w);
	nx[y]=z,pr[z]=y;
	if(y&&z<=n)rs+=ib(v-u);
}
inline void rev(int w){
	int x=pe[w],y=pr[x],z=nx[x],u=po[y],v=po[z];
	if(y&&z<=n)rs-=ib(v-u);
	nx[y]=x,pr[z]=x;
	if(y)rs+=ib(w-u);
	if(z<=n)rs+=ib(v-w);
}

int main(){
//	freopen("rrads.in","r",stdin);
//	freopen("rrads.out","w",stdout);
	
	scanf("%d%d",&n,&q);
	for (int i=1; i<=n; i++) scanf("%d",pe+i);
	for(int i=1,l,r;i<=q;++i){
        scanf("%d%d",&l,&r);
        qr[(l-1)/B+1].push_back(QR(i,l,r));
	}

	for(int i=1,x;(x=(i-1)*B+1)<=n;++i)if(qr[i].size()){
		std::sort(qr[i].begin(),qr[i].end(),[](const QR&a,const QR&b){return a.r>b.r;});
		init(x,n);
		int nl=x,nr=n;
		for(auto nw:qr[i]){
			for(;nr>nw.r;)del(nr),--nr;
			for(;nl<nw.l;)del(nl),++nl;
			ans[nw.w]=rs;
			for(;nl>x;)--nl,rev(nl);
		}
	}
	
	for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
	
	return 0;
}