#include<bits/stdc++.h>
#define ll long long
#define MAXN 500007
using namespace std;
int S=707;
int n,m,a[MAXN],p[MAXN],cnt;
ll rs[710][710],ans[MAXN];
int ls[MAXN];
struct data{
	int l,r;
}op[MAXN];

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int minn[710][710],maxx[710][710];
int pr[MAXN],nx[MAXN],v[710];
int pre[710][710],suc[710][710];

inline int calc(int x,int y){
	if(!x||!y||x>n||y>n)return 0;
	if (p[x]>p[y])
		return p[x]-p[y];
	else
		return p[y]-p[x];
}
/*
5 2
5 4 2 3 1
3 4
2 5

1
5
*/ 
int main(){
	n=read(),m=read(),cnt=n/S+1;
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=n;i++)
		p[a[i]]=i;
	for(int i=1;i<=m;i++)
		op[i].l=read(),op[i].r=read(),ls[i]=-1;
		
	
	for(int kk=1;kk<=cnt;kk++){
		int size=0;
		for(int i=1;i<=n;i++){
			if((i/S+1)==kk){
				++size;
				nx[i]=pr[i]=size;
				v[size]=a[i];
			}
			else 
				pr[i]=nx[i]=0;
		}
		
		int w=0;
		for(int i=1;i<=n;i++){
			if (pr[i])
				w=pr[i];
			else 
				pr[i]=w;
		}
		w=size+1;
		for(int i=n;i;i--){
			if (nx[i])
				w=nx[i];
			else
				nx[i]=w;
		}
		for(int i=1;i<=size;i++){
			minn[i][i]=maxx[i][i]=v[i];
			pre[i][i]=0,suc[i][i]=n+1;
			for(int j=i+1;j<=size;j++){
				suc[i][j]=suc[i][j-1],pre[i][j]=pre[i][j-1];
				minn[i][j]=min(minn[i][j-1],v[j]),maxx[i][j]=max(maxx[i][j-1],v[j]);
				if(v[j]<v[i])pre[i][j]=max(pre[i][j],v[j]);
				if(v[j]>v[i])suc[i][j]=min(suc[i][j],v[j]);
			}
		}
		
		for(int i=1;i<=size;i++){
			rs[i][i]=0;
			for(int j=i-1;j;j--){
				int sl=pre[j][i],sr=suc[j][i];
				rs[i][j]=rs[i][j+1]+calc(sl,v[j])+calc(v[j],sr)-calc(sl,sr);
			}
		}
		for(int i=1;i<=m;i++){
			int L=nx[op[i].l],R=pr[op[i].r];
			if(L<=R){
				ans[i]+=rs[R][L];
				if(~ls[i])
					ans[i]+=abs(p[minn[L][R]]-ls[i]);
				ls[i]=p[maxx[L][R]];
			}
		}
	}
	for(int i=1;i<=m;i++)
		printf("%lld\n",ans[i]);
	return 0;
}

answer.code:1:9: fatal error: bits/stdc++.h: No such file or directory
 #include<bits/stdc++.h>
         ^~~~~~~~~~~~~~~
compilation terminated.