#include<bits/stdc++.h>
using namespace std;typedef long long ll;
struct Precision{int x;Precision(int a){x=a;}};struct SW{int x;SW(int a){x=a;}};struct SF{int x;SF(int a){x=a;}};
#define Set(x,y,z) SW(x)<<SF(y)<<z<<SW(0)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define sid(i,u,a,b) for(int i=a[u],v;v=b[i].to,i;i=b[i].nex)
struct IO{
	#define Tp template<typename T>
	#define _D isdigit(c=gc())
	#define _A f|=eb;if(f)_R
	#define _R return *this
	#define _G p1==p2&&(p2=(p1=B)+fread(B,1,S,stdin),p1==p2)?EOF:*p1
	#define _T(x) while(st[++st[0]]=x%10+'0',x/=10)
	#define _O operator
	#define _P while(st[0])pc(st[st[0]--])
	static const int S=1<<21;char B[S],*p1,*p2,sf,t;int st[105],H,bs,sw;bool eb,f,w;IO(){bs=6;sf=eb=sw=0;}
	IO& _O >> (char&c){_A;while(T(c=gc())){_A;}_R;}char gc(){t=(_G++);t=='\r'&&nex()=='\n'&&(gc());t==EOF&&(eb=1);return t;}
	IO& _O >> (string&s){_A;s="";char c;while(T(c=gc())){_A;}while(s+=c,!T(c=gc()));_R;}void CL(){fwrite(B,1,H,stdout);H=0;}
	IO& _O >> (char*c){_A;while(T(*c=gc())){_A;}while(!T(*++c=gc()));*c=0;_R;}int P(char c){return c=='\n'||c=='\r'||c==EOF;}
	IO& _O >> (double&x){_A;x=0;bool F=0;char c;while(!_D){F^=(c=='-');_A;}while(x=x*10+(c^48),_D&&(P(c),1));if(c^'.')_R;c=gc();
		double k=1;while(x+=(c^48)*(k*=0.1),_D);F&&(x=-x);_R;}int T(char c){return c==' '||P(c);}_O bool()const{return !f;}
	Tp IO& _O >> (T&x){_A;x=0;bool F=0;char c;while(!_D){F^=(c=='-');_A;}while(x=(x<<3)+(x<<1)+(c^48),_D);F&&(x=-x);_R;}
	IO& _O << (const string &s){int l=s.length();pu(sw-l);rep(i,0,l-1)pc(s[i]);_R;}IO& _O << (SF x){sf=x.x;_R;}
	IO& _O << (char*c){int l=strlen(c);pu(sw-l);rep(i,0,l-1)pc(c[i]);_R;}IO& _O << (const char c){pc(c);_R;}~IO(){CL();}
	IO& _O << (const char*c){int l=strlen(c);pu(sw-l);rep(i,0,l-1)pc(c[i]);_R;}void pc(const char c){H==S&&(CL(),0);B[H++]=c;}
	IO& _O << (double x){w=0;x<0&&(w=1,x=-x);double t=0.5;rep(i,1,bs)t*=0.1;x+=t;ll y=x;_T(y);pu(sw-st[0]-w-bool(bs)-bs);
		w&&(pc('-'),0);_P;x-=ll(x);if(bs)pc('.');rep(i,1,bs)pc(int(x*=10)+'0'),x-=int(x);_R;}char nex(){return _G;}
	Tp IO& _O << (T x){x<0&&(pc('-'),x=-x);_T(x);pu(max(sw-st[0],0));_P;_R;}IO& _O << (Precision x){bs=x.x;_R;}
	IO& getline(string&s){_A;s="";char c=gc();if(!P(c))while(s+=c,!P(c=gc()));_R;}IO& _O << (SW x){sw=x.x;_R;}
	IO& getline(char*c){_A;*c=gc();if(!P(*c))while(!P(*++c=gc()));*c=0;_R;}void pu(int x){while(x-->0)pc(sf);}
}fin,fout;
const int N=5e5+10;
struct zj{
	int val,id;
	bool operator < (const zj &x)const{
		return val<x.val;
	}
}a[N];
set<zj>s;
int n,m,B,inx[N];ll now,ans[N];
struct ques{
	int l,r,id;
	bool operator < (const ques &x)const{
		return inx[l]^inx[x.l]?inx[l]<inx[x.l]:(inx[l]&1?r<x.r:r>x.r);
	}
}q[N];
set<zj>::iterator pre,nex;
void add(zj x){
	if(s.empty());
	else{
		pre=nex=s.lower_bound(x);
		if(nex!=s.end()&&nex!=s.begin()){
			pre--;now+=abs(x.id-(*pre).id)+abs(x.id-(*nex).id)-abs((*nex).id-(*pre).id);
		}
		else if(nex==s.end()){
			pre--;now+=abs(x.id-(*pre).id);
		}
		else now+=abs(x.id-(*nex).id);
	}
	s.insert(x);
}
void del(zj x){
	pre=nex=s.lower_bound(x);nex++;
	if(nex!=s.end()&&pre!=s.begin()){
		pre--;now-=abs(x.id-(*pre).id)+abs(x.id-(*nex).id)-abs((*nex).id-(*pre).id);
	}
	else if(nex==s.end()){
		pre--;now-=abs(x.id-(*pre).id);
	}
	else now-=abs(x.id-(*nex).id);
	s.erase(s.lower_bound(x));
}
int main(){
	fin>>n>>m;B=sqrt(n);for(int i=1;i<=n;i++)inx[i]=(i-1)/B+1,fin>>a[i].val,a[i].id=i;
	for(int i=1;i<=m;i++)fin>>q[i].l>>q[i].r,q[i].id=i;sort(q+1,q+1+m);
	int l=1,r=0;for(int i=1;i<=m;i++){
		while(r<q[i].r)add(a[++r]);while(l>q[i].l)add(a[--l]);
		while(r>q[i].r)del(a[r--]);while(l<q[i].l)del(a[l++]);
		ans[q[i].id]=now;
	}
	for(int i=1;i<=m;i++)fout<<ans[i]<<'\n';
	return 0;
}

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