#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
void read(int &res)
{
	res=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while('0'<=ch&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
}
void write(ll res)
{
	if(res>=10) write(res/10),putchar('0'+res%10);
	else putchar('0'+res);
}
const int N=5e5+100;
int n,m,a[N+10];
struct qst
{
	int l,r,id;
}p[N+10];
bool cmp(qst a,qst b){return a.r<b.r;}
int Rt[N+10],Cnt;
struct SEGpos
{
	int ls,rs,maxn;
}g[N*20];
#define mid (l+r>>1)
void updatepos(int &p,int l,int r,int x,int y)
{
	g[++Cnt]=g[p],p=Cnt,g[p].maxn=max(g[p].maxn,y);
	if(l==r) return;
	if(x<=mid) updatepos(g[p].ls,l,mid,x,y);
	else updatepos(g[p].rs,mid+1,r,x,y);
}
int querypos(int p,int l,int r,int L,int R)
{
	if(!p) return 0;
	if(L<=l&&r<=R) return g[p].maxn;
	int res=0;
	if(L<=mid) res=max(res,querypos(g[p].ls,l,mid,L,R));
	if(R>mid) res=max(res,querypos(g[p].rs,mid+1,r,L,R));
	return res;
}
#undef mid
int Find(int x,int l,int r){return querypos(Rt[x-1],1,n,l,r);}
ll ans[N+10],tree[N+10];
int lowbit(int x){return x&-x;}
void add(int x,int y){for(;x<=n;x+=lowbit(x)) tree[x]+=y;}
void add(int l,int r,int x){add(l,x),add(r+1,-x);}
ll query(int x)
{
	ll res=0;
	for(;x>0;x-=lowbit(x)) res+=tree[x];
	return res;
}
int rt[N+10],cnt;
struct SEG
{
	int ls,rs,sum;
}t[N*20];
#define mid (l+r>>1)
void update(int &p,int l,int r,int x)
{
	t[++cnt]=t[p],p=cnt,t[p].sum++;
	if(l==r) return;
	if(x<=mid) update(t[p].ls,l,mid,x);
	else update(t[p].rs,mid+1,r,x);
}
int querymin(int p1,int p2,int l,int r,int L)
{
	if(t[p2].sum-t[p1].sum==0) return n+1;
	if(l==r) return l;
	int res=n+1;
	if(L<=mid) res=querymin(t[p1].ls,t[p2].ls,l,mid,L);
	if(res==n+1) res=querymin(t[p1].rs,t[p2].rs,mid+1,r,L);
	return res;
}
int querymax(int p1,int p2,int l,int r,int R)
{
	if(t[p2].sum-t[p1].sum==0) return 0;
	if(l==r) return l;
	int res=0;
	if(R>mid) res=querymax(t[p1].rs,t[p2].rs,mid+1,r,R);
	if(res==0) res=querymax(t[p1].ls,t[p2].ls,l,mid,R);
	return res;
}
#undef mid
int Min(int l,int r,int L)
{
	if(l>r) return n+1;
	int res=querymin(rt[l-1],rt[r],1,n,L);
	return res;
}
int Max(int l,int r,int R)
{
	if(l>r) return 0;
	int res=querymax(rt[l-1],rt[r],1,n,R);
	return res;
}
void solve(int r)
{
	int las1,las2,res,tmp;
	las1=Find(r,1,a[r]);
	while(las1!=0)
	{
		las2=Find(las1,a[las1],a[r]),res=Min(las1+1,r-1,a[r]);
		tmp=Find(las1,a[las1],res);
		if(las2<tmp&&tmp<las1)
		{
			add(las2+1,tmp,-2*las1);
			if(res==n+1) add(tmp+1,las1,-las1);
		}
		else if(res==n+1) add(las2+1,las1,-las1);
		las1=las2;
	}
	las1=Find(r,a[r],n);
	while(las1!=0)
	{
		las2=Find(las1,a[r],a[las1]),res=Max(las1+1,r-1,a[r]);
		tmp=Find(las1,res,a[las1]);
		if(las2<tmp&&tmp<las1)
		{
			add(las2+1,tmp,-2*las1);
			if(res==0) add(tmp+1,las1,-las1);
		}
		else if(res==0) add(las2+1,las1,-las1);
		las1=las2;
	}
	res=Find(r,1,a[r]),add(1,res,r);
	res=Find(r,a[r],n),add(1,res,r);
}
int main()
{
	read(n),read(m);
	for(int i=1;i<=n;i++) read(a[i]),update(rt[i]=rt[i-1],1,n,a[i]),updatepos(Rt[i]=Rt[i-1],1,n,a[i],i);
	for(int i=1;i<=m;i++) read(p[i].l),read(p[i].r),p[i].id=i;
	sort(p+1,p+1+m,cmp);
	for(int i=1,r=0;i<=m;i++)
	{
		while(r<p[i].r) r++,solve(r);
		ans[p[i].id]=query(p[i].l);
	}
	for(int i=1;i<=m;i++) write(ans[i]),putchar('\n');
	return 0;
}
//it takes my code 7s to finish 500000subtask.what should I do.

answer.code:1:9: fatal error: cstdio: No such file or directory
 #include<cstdio>
         ^~~~~~~~
compilation terminated.