//#pragma GCC optimize(2)

#include<iostream>
#include<cmath>
using namespace std;

const int MAXN=5e5+5,B=700;
typedef long long ll;

//#define debug(a,len) printf("%s:",#a);for(int i=1;i<=len;++i)printf("%d ",a[i]);putchar('\n')
int N,a[MAXN],ia[MAXN];
int pre[MAXN],suf[MAXN],vis[MAXN],arr[MAXN];
int F[B+5][B+5],mn[B+5][B+5],mx[B+5][B+5];
void add(int l1,int r1,int l2,int r2,int k){
	//printf("add(%d,%d,%d,%d,%d)\n",l1,r1,l2,r2,k);
	F[l1][l2]+=k,F[l1][r2+1]-=k,F[r1+1][l2]-=k,F[r1+1][r2+1]+=k;
}

int M;
struct query{int l,r;}q[MAXN];ll ans[MAXN];int ed[MAXN];

int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>N>>M;
	for(int i=1;i<=N;++i)cin>>a[i],ia[a[i]]=i;
	for(int i=1;i<=M;++i)cin>>q[i].l>>q[i].r;
	for(int l=1;l<=N;l+=B){
		int r=min(N,l+B-1),len=r-l+1;
		//printf("[%d,%d] ==============\n",l,r);
		for(int i=l;i<=r;++i)vis[ia[i]]=1;
		int tmp=0;
		for(int i=1;i<=N;++i)if(vis[i])vis[i]=++tmp,arr[tmp]=a[i];
		//debug(vis,N);
		for(int i=1;i<=N;++i)pre[i]=vis[i]?vis[i]:pre[i-1];
		for(int i=N;i>=1;--i)suf[i]=vis[i]?vis[i]:suf[i+1];
		//debug(pre,N);
		//debug(suf,N);
		for(int i=l;i<=r;++i){
			int rig=len+1,lef=0;
			for(int j=i+1;j<=r;++j){
				//printf("i=%d,j=%d\n",i,j);
				if(ia[j]<ia[i]){
					if(lef<vis[ia[j]]){
						add(lef+1,vis[ia[j]],vis[ia[i]],rig-1,ia[i]-ia[j]);
						lef=vis[ia[j]];
					}
				}else{
					if(rig>vis[ia[j]]){
						add(lef+1,vis[ia[i]],vis[ia[j]],rig-1,ia[j]-ia[i]);
						rig=vis[ia[j]];
					}
				}
			}
		}
		for(int i=1;i<=len;++i)for(int j=i;j<=len;++j){
			F[i][j]+=F[i-1][j]+F[i][j-1]-F[i-1][j-1];
		}
		/*for(int i=1;i<=len;++i){
			for(int j=1;j<=len;++j)printf("%d ",F[i][j]);
			putchar('\n');
		}
		debug(arr,len);*/
		for(int i=1;i<=len;++i){
			mx[i][i]=mn[i][i]=arr[i];
			for(int j=i+1;j<=len;++j)mx[i][j]=max(mx[i][j-1],arr[j]),mn[i][j]=min(mn[i][j-1],arr[j]);
		}
		for(int i=1;i<=M;++i){
			int ll=suf[q[i].l],rr=pre[q[i].r];
			//printf("ll=%d,rr=%d\n",ll,rr);
			if(ll&&rr&&ll<=rr){
				//printf("ed[%d]=%d\n",i,ed[i]);
				if(ed[i])ans[i]+=abs(ia[mn[ll][rr]]-ed[i]);
				ans[i]+=F[ll][rr];
				ed[i]=ia[mx[ll][rr]];
				//printf("ans[%d]=%lld\n",i,ans[i]);
			}
		}
		for(int i=l;i<=r;++i)vis[ia[i]]=0;
		for(int i=1;i<=len;++i)for(int j=i;j<=len;++j)F[i][j]=0;
	}
	for(int i=1;i<=M;++i)cout<<ans[i]<<'\n';
	return 0;
}

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