#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
#define Debug(...) fprintf(stderr,__VA_ARGS__)
typedef long long ll;
const int N=5e5+5;
int Abs(int x){return x<0?-x:x;}
int n,m,a[N],bsiz,pos[N];
struct Fenwick{
	int t[N]={};
	void Add(int p,int k){for(;p<=n;p+=p&-p) t[p]+=k;}
	int QSum(int p){int res=0;for(;p;p-=p&-p) res+=t[p]; return res;}
	int QVal(int k){
		int p=0,s=0;
		Dec(i,20,0){
			if(p+(1<<i)>n||s+t[p+(1<<i)]>=k) continue;
			p+=1<<i,s+=t[p];
		}
		return p+1;
	}
	int QPre(int p){
		int s=QSum(p-1);
		return s?QVal(s):0;
	}
	int QNext(int p){return QVal(QSum(p)+1);}
};
namespace Mo{
	struct Query{
		int l,r,i;
		bool operator<(const Query &x){
			if(l/bsiz!=x.l/bsiz) return l<x.l;
			return ((l/bsiz)&1)?(r<x.r):(r>x.r);
		}
	}q[N];
	ll cur;Fenwick bit;
	void Oper(int x,int k){
		int pre=bit.QPre(x),nxt=bit.QNext(x);
		bit.Add(x,k);
		if(!pre&&nxt==n+1) return;
		if(nxt!=n+1) cur+=k*Abs(pos[nxt]-pos[x]);
		if(pre) cur+=k*Abs(pos[pre]-pos[x]);
		if(nxt!=n+1&&pre) cur+=-k*Abs(pos[nxt]-pos[pre]);
	}
	void Add(int x){Oper(x,1);}
	void Del(int x){Oper(x,-1);}
	ll ans[N];
	void Solve(){
		bsiz=max(1.,double(n)/sqrt(m));
		For(i,1,m) cin>>q[i].l>>q[i].r,q[i].i=i;
		sort(q+1,q+m+1);
		for(int i=1,l=1,r=0;i<=m;++i){
			if(q[i].l==q[i].r){
				ans[q[i].i]=0;continue;
			}
			while(l>q[i].l) Add(a[--l]);
			while(r<q[i].r) Add(a[++r]);
			while(l<q[i].l) Del(a[l++]);
			while(r>q[i].r) Del(a[r--]);
			ans[q[i].i]=cur;
		}
		For(i,1,m) cout<<ans[i]<<'\n';
	}
}
int main(){
	//freopen("rrads.in","r",stdin);
	//freopen("rrads.out","w",stdout);
	#ifndef zyz
	ios::sync_with_stdio(false),cin.tie(nullptr);
	#endif
	cin>>n>>m;
	For(i,1,n) cin>>a[i],pos[a[i]]=i;
	Mo::Solve();
	return 0;
}

answer.code:1:10: fatal error: iostream: No such file or directory
 #include <iostream>
          ^~~~~~~~~~
compilation terminated.