#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N=5e5+5;
int n,m,a[N],id[N],ql,qr;
int block,cnt,nd=1;
int tl[N],tr[N],nl[N],nr[N];
int rt,tot,rnd[N],tre[N],son[N][2],siz[N];
int sta[N<<1],cl[N<<1],cr[N<<1];
long long ans,ret[N],res;
struct A
{
	int Id,Ql,Qr;
	bool operator < (const A &x) const
	{
		return (Qr/block==x.Qr/block) ? Ql<x.Ql : Qr<x.Qr;
	}
}q[N];

int Abs (int x)
{
	return x>=0 ? x : -x;
}

void upd (int x)
{
	siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;
}

int newd (int x)
{
	++tot;
	siz[tot]=1;
	tre[tot]=x;
	rnd[tot]=rand();
	return tot;
}

int merge (int x,int y)
{
	if (!x||!y)  return x^y;
	if (rnd[x]>=rnd[y])
	{
		son[x][1]=merge(son[x][1],y);
		upd(x);
		return x;
	}
	else
	{
		son[y][0]=merge(x,son[y][0]);
		upd(y);
		return y;
	}
}

void split (int x,int qv,int &p1,int &p2)
{
	if (!x)
	{
		p1=0;
		p2=0;
		return ;
	}
	if (tre[x]<=qv)
	{
		p1=x;
		split(son[x][1],qv,son[p1][1],p2);
	}
	else
	{
		p2=x;
		split(son[x][0],qv,p1,son[p2][0]);
	}
	upd(x);
}

int kth (int x,int y)
{
	if (!x)  return 0;
	if (siz[son[x][0]]+1==y)  return tre[x];
	else if (siz[son[x][0]]>=y)  return kth(son[x][0],y);
	else  return kth(son[x][1],y-siz[son[x][0]]-1);
}

void sol (int x)
{
	int p1,p2,y,z;
	for (int i=nd;i<=x;++i)
	{
		split(rt,a[i],p1,p2);
		y=kth(p1,siz[p1]);
		z=kth(p2,1);
		if (!y&&!z)
		{
			rt=merge(merge(p1,newd(a[i])),p2);
			continue;
		}
		if (!y)
		{
			ans+=Abs(i-id[z]);
			tl[id[z]]=i;
			tr[i]=id[z];
		}
		else if (!z)
		{
			ans+=Abs(i-id[y]);
			tr[id[y]]=i;
			tl[i]=id[y];
		}
		else
		{
			ans-=Abs(id[z]-id[y]);
			ans+=Abs(id[z]-i)+Abs(id[y]-i);
			tl[id[z]]=i;
			tr[i]=id[z];
			tr[id[y]]=i;
			tl[i]=id[y];
		}
		rt=merge(merge(p1,newd(a[i])),p2);
//		cout <<ans<<endl;
	}
	nd=x+1;
}

void dell (int x)
{
	int y=nl[x],z=nr[x];
	if (!y)
	{
		nl[z]=0;
		res-=Abs(x-z);
	}
	else if (!z)
	{
		nr[y]=0;
		res-=Abs(x-y);
	}
	else
	{
		nl[z]=y;
		nr[y]=z;
		res-=Abs(x-z)+Abs(x-y);
		res+=Abs(y-z);
	}
}

void delr (int x)
{
	int y=nl[x],z=nr[x];
	if (!y)
	{
		++cnt;
		sta[cnt]=z;
		cl[cnt]=nl[z];
		cr[cnt]=nr[z];
		nl[z]=0;
		res-=Abs(x-z);
	}
	else if (!z)
	{
		++cnt;
		sta[cnt]=y;
		cl[cnt]=nl[y];
		cr[cnt]=nr[y];
		nr[y]=0;
		res-=Abs(x-y);
	}
	else
	{
		++cnt;
		sta[cnt]=y;
		cl[cnt]=nl[y];
		cr[cnt]=nr[y];
		++cnt;
		sta[cnt]=z;
		cl[cnt]=nl[z];
		cr[cnt]=nr[z];
		nl[z]=y;
		nr[y]=z;
		res-=Abs(x-z)+Abs(x-y);
		res+=Abs(y-z);
	}
}

void solve1 ()
{
	for (int i=1;i<=n;++i)
	{
		scanf ("%d",&a[i]);
		id[a[i]]=i;
	}
	while (m--)
	{
		scanf ("%d%d",&ql,&qr);
		int x=0;
		ans=0;
		for (int j=n;j>=1;--j)
		{
			if (id[j]>=ql&&id[j]<=qr)
			{
				if (x)  ans+=Abs(x-id[j]);
				x=id[j];
			}
		}
		printf ("%lld\n",ans);
	}
}

void solve2 ()
{
	block=(int)sqrt(n);
	for (int i=1;i<=n;++i)
	{
		scanf ("%d",&a[i]);
		id[a[i]]=i;
	}
	for (int i=1;i<=m;++i)
	{
		scanf ("%d%d",&q[i].Ql,&q[i].Qr);
		q[i].Id=i;
	}
	sort (q+1,q+m+1);
//	for (int i=1;i<=m;++i)
//	{
//		cout <<q[i].Ql<<' '<<q[i].Qr<<endl;
//	}
	int L=1,R=block-1,X=block-1;
	for (int i=1;i<=m;++i)
	{
		ql=q[i].Ql,qr=q[i].Qr;
//		cout <<qr<<' '<<X<<endl;
		if (qr/block!=X/block)
		{
			X=min(qr/block*block+block-1,n);
			L=1;
			R=X;
			sol(R);
//			cout <<ans<<endl;
			for (int i=1;i<=R;++i)
			{
				nl[i]=tl[i];
				nr[i]=tr[i];
			}
			res=ans;
		}
		while (L<ql)  dell(L++);
		long long x=res;
		while (R>qr)  delr(R--);
		ret[q[i].Id]=res;
		while (cnt)
		{
			int y=sta[cnt];
			nl[y]=cl[cnt];
			nr[y]=cr[cnt];
			--cnt;
		}
		R=X;
		res=x;
	}
	for (int i=1;i<=m;++i)
	{
		printf ("%lld\n",ret[i]);
	}
}

int main ()
{
//	freopen ("rrads.in","r",stdin);
//	freopen ("rrads.out","w",stdout);
	srand(time(0));
	scanf ("%d%d",&n,&m);
//	if (1LL*n*m<=300000000LL)  solve1();
//	else  solve2();
	solve2();
	return 0;
}