#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define N 500000
#define M 500000
#define mod 998244353
#define Mod (mod-1)
#define eps (1e-5)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define d(x,y) (m*x+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound 
using namespace std;
struct IO{
    static const int S=1<<21;
    char buf[S],*p1,*p2;int st[105],Top;
    ~IO(){clear();}
    inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
    inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}
    template<typename T>inline IO&operator >> (T&x){
        x=0;bool f=0;char ch=gc();
        while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        f?x=-x:0;return *this;
    }
    inline IO&operator << (const char c){pc(c);return *this;}
    template<typename T>inline IO&operator << (T x){
        if(x<0) pc('-'),x=-x;
        do{st[++st[0]]=x%10,x/=10;}while(x);
        while(st[0]) pc('0'+st[st[0]--]);return *this;
    }
}fin,fout;
int n,m,k,x,y,A[N+5],Id[N+5],L[N+5],R[N+5],Fl[N+5],Ns,He;ll Ans,ToT[N+5];
struct Ques{int l,r,id;};vector<Ques> S[N+5];I bool C1(Ques x,Ques y){return x.r>y.r;}
I void Del(int x){R[A[x]]<=n&&(Ans-=abs(Id[R[A[x]]]-x)),L[A[x]]&&(Ans-=abs(x-Id[L[A[x]]])),R[L[A[x]]]=R[A[x]],L[R[A[x]]]=L[A[x]],R[A[x]]<=n&&L[A[x]]&&(Ans+=abs(Id[L[A[x]]]-Id[R[A[x]]]));}
I void Ins(int x){R[A[x]]<=n&&L[A[x]]&&(Ans-=abs(Id[L[A[x]]]-Id[R[A[x]]]));R[L[A[x]]]=A[x],L[R[A[x]]]=A[x];L[A[x]]&&(Ans+=abs(x-Id[L[A[x]]]));R[A[x]]<=n&&(Ans+=abs(x-Id[R[A[x]]]));}
int main(){
//	freopen("rrads.in","r",stdin);freopen("rrads.out","w",stdout);
	RI i,j,h;fin>>n>>m;k=max(n/sqrt(m),1);for(i=1;i<=n;i++)fin>>A[i],Id[A[i]]=i;for(i=1;i<=m;i++) fin>>x>>y,S[x/k].push_back((Ques){x,y,i});
	for(i=0;i<=n/k;i++){if(!S[i].size()) continue;
		sort(S[i].begin(),S[i].end(),C1);Me(Fl,0);for(j=max(i*k,1);j<=S[i][0].r;j++) Fl[A[j]]=1;Fl[0]=Fl[n+1]=1;
		for(Ans=Ns=0,j=1;j<=n+1;j++) Fl[j]&&(L[j]=Ns,Ns&&j<=n&&(Ans+=abs(Id[j]-Id[Ns])),Ns=j);for(Ns=n+1,j=n;~j;j--) Fl[j]&&(R[j]=Ns,Ns=j);
		for(He=S[i][0].r,j=0;j<S[i].size();j++){
			while(He>S[i][j].r) Del(He),He--;
			for(h=max(i*k,1);h<S[i][j].l;h++) Del(h);
			ToT[S[i][j].id]=Ans;for(h=S[i][j].l-1;h>=max(i*k,1);h--) Ins(h);
		}
	}for(i=1;i<=m;i++) fout<<ToT[i]<<'\n';
}

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