#include <bits/stdc++.h>
#define il inline
#define ll long long
#define pb push_back
const int N=5e5+5,B=120;

namespace IO
{
	const int S=1<<20|500; char I[S+5],*s,*t,O[S+5],*o; int p[40],P;

	il char Gc(){if (t==s){t=(s=I)+fread(I,1,1<<20,stdin); if (t==s) return EOF;} return *s++;}

	template<class T> il void Read(T &x)
	{
		char c; while ((c=Gc())<48||c>57); x=c^48;
		while ((c=Gc())>47&&c<58) x=(x<<3)+(x<<1)+(c^48);
	}

	il void Fs(){if (o-O) fwrite(O,1,o-O,stdout); o=O;}
	
	il void Pc(char c){if (*o++=c,o-O==S) Fs();}

	template<class T> il void Print(T x){T y; do y=x/10,p[P++]=x-10*y;while (x=y); while (P) Pc(p[--P]^48);}
	
	struct F{F(){o=O;} ~F(){Fs();}}FF;
}
using IO::Read; using IO::Print; using IO::Pc;

int n,m,a[N],b[N],st[N],tp,L[N],R[N]; ll E,ans[N]; struct node{int l,r,o;}; std::vector<node> g[N]; 

il int Dis(int x,int y){return !x||x>n||!y||y>n?0:std::abs(b[x]-b[y]);}

il void Del(int x){st[++tp]=x,E+=Dis(L[x],R[x])-Dis(x,L[x])-Dis(x,R[x]),L[R[x]]=L[x],R[L[x]]=R[x];}

il void Undo(){int x=st[tp--]; E+=Dis(x,L[x])+Dis(x,R[x])-Dis(L[x],R[x]),L[R[x]]=x,R[L[x]]=x;}

int main()
{
	sdcanf("%d%d",&n,&m); int i,j,l,r;
	for (i=1; i<=n; i++) scanf("%d",a+i),b[a[i]]=i;
	for (i=1; i<=m; i++) scanf("%d%d",&l,&r),g[(l-1)/B+1].pb({l,r,i});

	for (j=1; j<=n; j+=B)
	{
		std::vector<node> &h=g[(j-1)/B+1]; std::sort(h.begin(),h.end(),[](const node &a,const node &b){return a.r==b.r?(a.l==b.l?a.o<b.o:a.l<b.l):a.r>b.r;});
		for (i=j,E=tp=0; i<=n; i++) L[i]=i-1,R[i]=i+1,E+=Dis(i,R[i]); L[j]=0;
		l=j,r=n; for (node v:h)
		{
			for ( ; r>v.r; r--) Del(a[r]);
			for ( ; l<v.l; l++) Del(a[l]);
			for (ans[v.o]=E; l>j; l--) Undo();
		}
	}
	for (i=1; i<=m; i++) printf("%lld\n",ans[i]);

	return 0;
}

answer.code: In function ‘int main()’:
answer.code:39:9: error: ‘sdcanf’ was not declared in this scope; did you mean ‘sscanf’?
   39 |         sdcanf("%d%d",&n,&m); int i,j,l,r;
      |         ^~~~~~
      |         sscanf
answer.code:40:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   40 |         for (i=1; i<=n; i++) scanf("%d",a+i),b[a[i]]=i;
      |                              ~~~~~^~~~~~~~~~
answer.code:41:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   41 |         for (i=1; i<=m; i++) scanf("%d%d",&l,&r),g[(l-1)/B+1].pb({l,r,i});
      |                              ~~~~~^~~~~~~~~~~~~~