#include<bits/stdc++.h>
using namespace std;
namespace file_read{
    namespace input_file_io{
        char ib[1<<26],*ip1=ib,*ip2=ib;
        inline char gc(){
            return (ip1==ip2&&(ip2=(ip1=ib)+fread(ib,1,1<<24,stdin)),
			ip1==ip2?EOF:*ip1++);
        }
        inline int read(){
            int x=0;
            char c=gc();
            while(c<'0'||c>'9'){
            	c=gc();
			}
            while(c>='0'&&c<='9'){
                x=(x<<3)+(x<<1)+(c^'0');
                c=gc();
            }
            return x;
        }
        inline auto read2(){
        	long long x=0;
            char c=gc();
            while(c<'0'||c>'9'){
            	c=gc();
			}
            while(c>='0'&&c<='9'){
                x=(x<<3)+(x<<1)+(c^'0');
                c=gc();
            }
            return x;
		}
    };
    namespace output_file_io{
        char ob[1<<26],*op=ob;
        inline void pc(char c){
            *op++=c;
        }
        void write(auto x){
            if(x<0){
                pc('-');
                x=-x;
            }
            if(x==0)pc('0');
            static int number_stack[40];
            int total_count=0;
            while(x)number_stack[++total_count]=x%10,x/=10;
            while(total_count){
                pc(number_stack[total_count]+'0');
                --total_count;
            }
        }
        inline void final_write(){
            fwrite(ob,op-ob,1,stdout);
        }
    };
    using namespace input_file_io;
    using namespace output_file_io;
};
using namespace file_read;
inline int Abs(int x){
	return x>0?x:-x;
}
int L[500005],R[500005];
int nxt[500005],pre[500005];
int a[500005],b[500005];
int bl[500005];
long long an[500005];
struct apple{
	int wz,l,r;
	bool operator<(const apple &other)const{
		if(bl[l]!=bl[other.l])return l<other.l;
		return r<other.r;
	}
}e[500005];
struct syz{
	int wz,zz,zx;
	syz(int wz=0,int zz=0,int zx=0):
		wz(wz),zz(zz),zx(zx){}
};
int n,m;
int aa[500005],bb[500005];
long long ans;
inline int calc(int x,int y){
	if(x!=0&&y!=0&&x!=n+1&&y!=n+1)return Abs(x-y);
	return 0;
}
stack<syz>vc;
void del(int x,int bh){
	if(bh==1){
		vc.emplace(syz(pre[x],1,x));
		vc.emplace(syz(nxt[x],0,x));
	}
	ans-=calc(b[x],b[pre[x]]);
	ans-=calc(b[x],b[nxt[x]]);
	ans+=calc(b[pre[x]],b[nxt[x]]);
	nxt[pre[x]]=nxt[x];
	pre[nxt[x]]=pre[x];
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i)a[i]=read(),b[a[i]]=i;
	b[0]=0,b[n+1]=n+1;
	for(int i=1;i<=n;++i)aa[i]=a[i];
	int S=sqrt(n+0.5);
	int SS=(n-1)/S+1;
	for(int i=1;i<SS;++i){
		L[i]=(i-1)*S+1,R[i]=i*S;
		for(int j=L[i];j<=R[i];++j)bl[j]=i;
	}
	L[SS]=(SS-1)*S+1,R[SS]=n;
	for(int j=L[SS];j<=R[SS];++j)bl[j]=SS;
	for(int i=1;i<=m;++i){
		e[i].wz=i;
		e[i].l=read();
		e[i].r=read();
	}
	sort(e+1,e+m+1);
	int ll=1,rr=0;
	for(int i=0;i<=n+1;++i){
		pre[i]=0;
		nxt[i]=n+1;
	}
	int wz=m;
	aa[0]=0,aa[n+1]=n+1;
	for(int i=SS;i>=1;--i){
		ll=L[i],rr=n;
		sort(aa+L[i],aa+R[i]+1);
		merge(aa+L[i],aa+R[i]+1,aa+R[i]+1,aa+n+1,bb+L[i]);
		for(int j=L[i];j<=n;++j)aa[j]=bb[j],bb[j]=0;
		int ss=aa[L[i]-1];
		aa[L[i]-1]=0;
		ans=0;
		for(int j=L[i];j<=n;++j){
			pre[aa[j]]=aa[j-1];
			ans+=calc(b[aa[j-1]],b[aa[j]]);
			nxt[aa[j]]=aa[j+1];
		}
		while(wz>=1&&bl[e[wz].l]==i){
			while(rr>e[wz].r)del(a[rr--],0);
			while(ll<e[wz].l)del(a[ll++],1);
			an[e[wz].wz]=ans;
			--wz;
			while(vc.size()){
				auto at=vc.top();
				if(at.zz==1)nxt[at.wz]=at.zx;
				else pre[at.wz]=at.zx;
				vc.pop();
			}
			ll=L[i];
		}
		aa[L[i]-1]=ss;
	}
	for(int i=1;i<=m;++i)write(an[i]),pc('\n');
	final_write();
	return 0;
}