#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define endl putchar('\n')
const int N=500005;
typedef long long ll;
using namespace std;

int n,m,a[N],rv[N];
ll ans[N];

struct tire {
	#define int unsigned
	int ch[1050][32],s[1050],cnt,c[1050];
	int get(int x,int d) {
		int msk=(1<<5)-1;
		return (x>>(5*d))&msk;
	}
	int highbit(int x) { return 1<<(31-__builtin_clz(x)); }
	int lowbit(int x) { return x&-x; }
	void insert(int x) {
		int t=get(x,1),p=get(x,0),&a=ch[0][t];
		s[0]|=1<<t; if(!a) a=++cnt;
		int &b=ch[a][p];
		s[a]|=1<<p; if(!b) b=++cnt;
		if(!c[b]) c[b]++,c[a]++,c[0]++;
	}
	void erase(int x) {
		int t=get(x,1),p=get(x,0),a=ch[0][t];
		if(!a) return;
		int b=ch[a][p];
		if(!b) return;
		if(c[b]) {
			c[b]--,c[a]--,c[0]--;
			s[a]^=1<<p;
			if(!c[a]) s[0]^=1<<t;
		}
	}
	signed prev(int x) {
		if(!c[0]) return -1;
		int t=get(x,1),p=get(x,0),a=ch[0][t];
		if(a&&c[a]) {
			if(s[a]&((1<<p)-1)) return (t<<5)|__builtin_ctz(highbit(s[a]&((1<<p)-1)));
		}
		if(s[0]&((1<<t)-1)) {
			int q=__builtin_ctz(highbit(s[0]&((1<<t)-1)));
			int p=__builtin_ctz(highbit(s[ch[0][q]]));
			return (q<<5)|p;
		}
		return -1;
	}
	signed next(int x) {
		if(!c[0]) return -1;
		int t=get(x,1),p=get(x,0),a=ch[0][t];
		if(a&&c[a]&&p!=31) {
			int nw=(s[a]>>(p+1))<<(p+1);
			if(nw) return (t<<5)|__builtin_ctz(lowbit(nw));
		}
		if(t==31) return -1;
		int nw=(s[0]>>(t+1))<<(t+1);
		if(nw) {
			int q=__builtin_ctz(lowbit(nw));
			int p=__builtin_ctz(lowbit(s[ch[0][q]]));
			return (q<<5)|p;
		}
		return -1;
	}
	#undef int
} t[800];

namespace ran {
	int bel[N],lf[N],rt[N],blk,tot;
	ll sum[N];
	void init() {
		rep(i,1,n) bel[i]=(i-1)/blk+1;
		tot=bel[n];
		rep(i,1,tot) lf[i]=(i-1)*blk+1,rt[i]=i*blk;
	}
	void insert(int x) {
		int b=bel[a[x]],v=a[x]-lf[b]+1;
		int pre=t[b].prev(v),nex=t[b].next(v);
		if(pre!=-1) pre+=lf[b]-1;
		if(nex!=-1) nex+=lf[b]-1;
		if(pre!=-1&&nex!=-1) {
			sum[b]-=abs(rv[pre]-rv[nex]);
			sum[b]+=abs(rv[pre]-x)+abs(rv[nex]-x);
		} else if(pre!=-1) sum[b]+=abs(rv[pre]-x);
		else if(nex!=-1) sum[b]+=abs(rv[nex]-x);
		t[b].insert(v);
	}
	void erase(int x) {
		int b=bel[a[x]],v=a[x]-lf[b]+1;
		int pre=t[b].prev(v),nex=t[b].next(v);
		if(pre!=-1) pre+=lf[b]-1;
		if(nex!=-1) nex+=lf[b]-1;
		if(pre!=-1&&nex!=-1) {
			sum[b]+=abs(rv[pre]-rv[nex]);
			sum[b]-=abs(rv[pre]-x)+abs(rv[nex]-x);
		} else if(pre!=-1) sum[b]-=abs(rv[pre]-x);
		else if(nex!=-1) sum[b]-=abs(rv[nex]-x);
		t[b].erase(v);
	}
	ll query() {
		int pre=-1;
		ll res=0;
		rep(i,1,tot) {
			res+=sum[i];
			int mn=t[i].next(0);
			if(mn!=-1) mn+=lf[i]-1;
			if(pre!=-1&&mn!=-1) res+=abs(rv[mn]-rv[pre]);
			int nw=t[i].prev(1001);
			if(nw!=-1) pre=nw+lf[i]-1;
		}
		return res;
	}
}

namespace seq{
	int bel[N],lf[N],rt[N],blk,tot,L,R;
	struct ques {
		int l,r,id;
		bool operator < (const ques &x) const { return bel[l]==bel[x.l]?r<x.r:bel[l]<bel[x.l]; }
	} q[N];
	void init() {
		rep(i,1,n) bel[i]=(i-1)/blk+1;
		tot=bel[n];
		rep(i,1,tot) lf[i]=(i-1)*blk+1,rt[i]=i*blk;
	}
	void insert(int x) {
		ran::insert(x);
	}
	void erase(int x) {
		ran::erase(x);
	}
	void solve() {
		sort(q+1,q+m+1);
		rep(i,1,m) {
			while(R<q[i].r) insert(++R);
			while(L>q[i].l) insert(--L);
			while(R>q[i].r) erase(R--);
			while(L<q[i].l) erase(L++);
			ans[q[i].id]=ran::query();
		}
	}
}

void init() {
	seq::init(),ran::init();
}

void solve() {
	seq::solve();
}

void file() {
	freopen("data.txt","r",stdin);
	freopen("yours.txt","w",stdout);
}

int main() {
//	file();
//	printf("%lf\n",1.0*sizeof t/1024/1024);
	scanf("%d%d",&n,&m),seq::blk=150,ran::blk=1000;
	rep(i,1,n) scanf("%d",&a[i]),rv[a[i]]=i;
	rep(i,1,m) {
		int l,r; scanf("%d%d",&l,&r);
		seq::q[i]={l,r,i};
	}
	init();
	solve();
	rep(i,1,m) printf("%lld\n",ans[i]);
	return 0;
}