#include<bitsdc++.h>
#define MAXN 600005
typedef long long ll;
using namespace std;

int n,m,a[MAXN],part,rk[MAXN];
struct node{int L,R,yl;}t[MAXN];

bool cmp(node A , node B){
	if(rk[A.L] == rk[B.L])return A.R > B.R;
	return rk[A.L] < rk[B.L];
}

//处理出初始的  

ll ans[MAXN];
int ycl_L[MAXN],ycl_R[MAXN];
int now_L[MAXN],now_R[MAXN];
ll ycl_ans , now_ans , zz_ans;

struct node2{int dx,dy;}p[MAXN];
bool cmp2(node2 A , node2 B){return A.dx < B.dx;}

vector<int>belong[805];

void ycl(){
	int zz = 0;
	for(int i = 1 ; i <= n ; i++)zz++ , p[zz].dx = a[i] , p[zz].dy = i;
	sort(p + 1 , p + 1 + zz , cmp2);
	for(int i = 1 ; i <= zz ; i++){
		if(i != zz)ycl_ans += abs(p[i].dy - p[i + 1].dy);
		ycl_R[p[i].dy] = p[i + 1].dy;
		if(i != zz)ycl_L[p[i + 1].dy] = p[i].dy;
	}
}


void YCL(){
	scanf("%d%d" , &n , &m) , part = sqrt(n);
	for(int i = 1 ; i <= n ; i++)scanf("%d" , &a[i]);
	for(int i = 1 ; i <= n ; i++)rk[i] = (i - 1) / part + 1;
	for(int i = 1 ; i <= m ; i++)t[i].yl = i , scanf("%d%d" , &t[i].L , &t[i].R);
	sort(t + 1 , t + 1 + m , cmp);
	for(int i = 1 ; i <= m ; i++)belong[rk[t[i].L]].push_back(i);
	ycl();
}


void ycl_del(int pos){
	int l = ycl_L[pos] , r = ycl_R[pos];
	if(l){
		ycl_ans = ycl_ans - 1ll * abs(pos - l);
		ycl_R[l] = r;
	}
	if(r){
		ycl_ans = ycl_ans - 1ll * abs(pos - r);
		ycl_L[r] = l;
	}
	if(l && r)ycl_ans = ycl_ans + 1ll * abs(l - r);
}

int len;
struct node3{int tp,pos,val;}q[MAXN];

void now_del(int pos){
	int l = now_L[pos] , r = now_R[pos];
	if(l){
		now_ans = now_ans - 1ll * abs(pos - l);
		len++ , q[len].tp = 1 , q[len].pos = l , q[len].val = now_R[l];
		now_R[l] = r;
	}
	if(r){
		now_ans = now_ans - 1ll * abs(pos - r);
		len++ , q[len].tp = 0 , q[len].pos = r , q[len].val = now_L[r];
		now_L[r] = l;
	}
	if(l && r)now_ans = now_ans + 1ll * abs(l - r);
}



void solve(){
	
	for(int i = 1 ; i <= rk[n] ; i++){
		memcpy(now_L , ycl_L , sizeof(ycl_L));
		memcpy(now_R , ycl_R , sizeof(ycl_R));
		now_ans = ycl_ans;
		
		
		int nowL = (i - 1) * part + 1 , nowR = n;
		for(int now = 0 ; now < belong[i].size() ; now++){
			while(nowR > t[belong[i][now]].R)now_del(nowR) , nowR--;
			
			zz_ans = now_ans;
			
			len = 0;
			while(nowL < t[belong[i][now]].L)now_del(nowL) , nowL++;
			
			
			ans[t[belong[i][now]].yl] = now_ans;
			
			while(len){
				if(q[len].tp == 0)now_L[q[len].pos] = q[len].val;
				else now_R[q[len].pos] = q[len].val;
				len--;
			}
			
			now_ans = zz_ans , nowL = (i - 1) * part + 1;
		
			
		}
	
		
		int L = (i - 1) * part + 1 , R = part * i;
		for(int j = L ; j <= R ; j++)ycl_del(j);
		
	}
	
	for(int i = 1 ; i <= m ; i++)printf("%lld\n" , ans[i]);
	
}

int main(){
	memset(ans , 0 , sizeof(ans));
	YCL();
	solve();
}

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