/*
after dusk passed,
there is a starry sky.
*/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define m_k make_pair
#define ls x+x
#define rs x+x+1
#define int long long
#define len(a) (int)a.size()
using namespace std;
const int N=5*1e5+100;
int n,m,a[N],L[N],R[N],ans[N],tr[N],b[N],w;
inline int read()
{
	int f=1,x=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	return x*f;
}
struct bit
{
	int sh[N],ti[N],dfn;
	int lowbit(int x){return x&(-x);}
	void upd(int x){if(ti[x]!=dfn)ti[x]=dfn,sh[x]=0;}
	void change(int x,int v){while(x<=n)upd(x),sh[x]+=v,x+=lowbit(x);}
	int query(int x){int ans=0;while(x)upd(x),ans+=sh[x],x-=lowbit(x);return ans;}
}T;
namespace seg
{
	int MIN[N],ti[N],dfn;
	void upd(int x){if(ti[x]!=dfn)ti[x]=dfn,MIN[x]=n+1;}
	void pushup(int x)
	{
		upd(ls),upd(rs);
		MIN[x]=min(MIN[ls],MIN[rs]);
	}
	void change(int x,int l,int r,int wh,int v)
	{
		upd(x);MIN[x]=min(MIN[x],v);
		if (l==r) return;
		int mid=(l+r)>>1;
		if (wh<=mid) change(ls,l,mid,wh,v);
		else change(rs,mid+1,r,wh,v);
	}
	int query(int x,int l,int r,int ll,int rr)
	{
		upd(x);
		if (ll<=l&&rr>=r) return MIN[x];
		int mid=(l+r)>>1,ans=n+1;
		if (ll<=mid) ans=min(ans,query(ls,l,mid,ll,rr));
		if (rr>mid) ans=min(ans,query(rs,mid+1,r,ll,rr));
		return ans;
	}
}
vector <int> sh[N*4],sp[N*4];
void change(int x,int l,int r,int ll,int rr,int v)
{
	if (ll<=l&&rr>=r){sp[x].push_back(v);return;}
	int mid=(l+r)>>1;
	if (ll<=mid&&rr>=mid) sh[x].push_back(v);
	if (ll<=mid) change(ls,l,mid,ll,rr,v);
	if (rr>mid) change(rs,mid+1,r,ll,rr,v);
}
void cal(int x,int l,int r,int op)
{
	int mid=(l+r)>>1;
	if (op) mid=r+l-mid;
	T.dfn++;seg::dfn++;
	for (int i=l;i<=r;i++) tr[a[i]]=i;
	for (int i=mid+(op==0);i<=r;i++) seg::change(1,1,n,a[i],i);
	sort(sh[x].begin(),sh[x].end(),[](int a,int b){return L[a]>L[b];});
	set <int> s;int pos=mid-(op==1);
	for (int i:sh[x])
	{
		int nl=max(L[i],l),nr=min(R[i],r);
		while (pos>=nl)
		{
			auto it=s.insert(a[pos]).first;
			auto add=[&](int x,int y,int v)
			{
				int wh=seg::query(1,1,n,x,y);
				T.change(wh,v*(mid-tr[x]+mid-tr[y]-abs(tr[x]-tr[y])));
			};
			if (it!=s.begin()&&next(it)!=s.end())
			{
				add(*prev(it),*next(it),-1);
				add(*it,*next(it),1);add(*prev(it),*it,1);
			}
			if (it==s.begin())
			{
				int x,y,wh;
				if (next(it)!=s.end())
				{
					x=*next(it);wh=seg::query(1,1,n,1,x);
					T.change(wh,-(mid-tr[x]));
					add(*it,*next(it),1);
				}
				x=*it;wh=seg::query(1,1,n,1,x);
				T.change(wh,mid-tr[x]);
			}
			if (next(it)==s.end())
			{
				int x,y,wh;
				if (it!=s.begin())
				{
					x=*prev(it);wh=seg::query(1,1,n,x,n);
					T.change(wh,-(mid-tr[x]));
					add(*prev(it),*it,1);
				}
				x=*it;wh=seg::query(1,1,n,x,n);
				T.change(wh,mid-tr[x]);
			}
			pos--;
		}
		ans[i]+=T.query(nr);
	}
}
void solve(int x,int l,int r)
{
	for (int i=l;i<=r;i++) tr[a[i]]=i;
	memcpy(b+1,a+l,(r-l+1)*sizeof(int));
	sort(b+1,b+1+r-l+1);
	int sum=0;
	for (int i=1;i<r-l+1;i++) sum+=abs(tr[b[i]]-tr[b[i+1]]);
	for (int i:sp[x]) ans[i]+=sum;
	if (l==r) return;
	int mid=(l+r)>>1;
	cal(x,l,r,0);
	reverse(a+l,a+r+1);
	for (int i:sh[x]) L[i]=r+l-L[i],R[i]=r+l-R[i],swap(L[i],R[i]);
	cal(x,l,r,1);
	reverse(a+l,a+r+1);
	for (int i:sh[x]) L[i]=r+l-L[i],R[i]=r+l-R[i],swap(L[i],R[i]);
	solve(ls,l,mid);
	solve(rs,mid+1,r);
}
signed main()
{
	n=read();m=read();
	for (int i=1;i<=n;i++) a[i]=read();
	for (int i=1;i<=m;i++)
	{
		L[i]=read(),R[i]=read();
		change(1,1,n,L[i],R[i],i);
	}
	solve(1,1,n);
	for (int i=1;i<=m;i++) printf("%lld\n",ans[i]);
}