#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5+5;
ll id,n,q,a[N],b[N],stak1[N],stak2[N],top1,top2;
ll ans[N];
struct info{
	ll len,S,Sx,Sy,Sxy;
}t1[N<<2];
struct tag{
	ll cx,cy,ax,ay,axy,a;	
}t2[N<<2];
#define lc k<<1
#define rc k<<1|1
#define ls lc,l,mid
#define rs rc,mid+1,r
info merge(info x,tag y){
	x.S+=x.Sx*y.ax+x.Sy*y.ay+x.Sxy*y.axy+x.len*y.a;
	if(y.cx){
		x.Sx=x.len*y.cx;
		x.Sxy=x.Sy*y.cx;
	}
	if(y.cy){
		x.Sy=x.len*y.cy;
		x.Sxy=x.Sx*y.cy;
	}
	return x;
}
tag merge(tag x,tag y){
	if(x.cx&&x.cy)
		x.a+=y.axy*x.cx*x.cy+y.ax*x.cx+y.ay*x.cy+y.a;
	else
		if(x.cx){
			x.ay+=y.axy*x.cx+y.ay;
			x.a+=y.ax*x.cx+y.a;
		}
		else
			if(x.cy){
				x.ax+=y.axy*x.cy+y.ax;
				x.a+=y.ay*x.cy+y.a;
			}
			else{
				x.axy+=y.axy;
				x.ax+=y.ax;
				x.ay+=y.ay;
				x.a+=y.a;
			}
	if(y.cx) x.cx=y.cx;
	if(y.cy) x.cy=y.cy;
	return x;
}
void pushdown(int k){
	t1[lc]=merge(t1[lc],t2[k]);
	t2[lc]=merge(t2[lc],t2[k]);
	
	t1[rc]=merge(t1[rc],t2[k]);
	t2[rc]=merge(t2[rc],t2[k]);
	
	t2[k]=(tag){0,0,0,0,0,0};
}
void pushup(int k){
	t1[k].S=t1[lc].S+t1[rc].S;
	t1[k].Sx=t1[lc].Sx+t1[rc].Sx;
	t1[k].Sy=t1[lc].Sy+t1[rc].Sy;
	t1[k].Sxy=t1[lc].Sxy+t1[rc].Sxy;
}
void pre(int k,int l,int r){
	t1[k].len=r-l+1;
	if(l==r){
		t1[k].Sy=1;
		return ;
	}
	int mid=l+r>>1;
	pre(ls);
	pre(rs);
	pushup(k);
}
void change(int k,int l,int r,int x,int y,tag d){
	if(x<=l&&r<=y){
		t1[k]=merge(t1[k],d);
		t2[k]=merge(t2[k],d);
		return ;
	}
	int mid=l+r>>1;
	pushdown(k);
	if(x<=mid) change(ls,x,y,d);
	if(mid<y) change(rs,x,y,d);
	pushup(k);
}
ll query(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)
		return t1[k].S;
	int mid=l+r>>1;
	ll res=0;
	pushdown(k);
	if(x<=mid) res+=query(ls,x,y);
	if(mid<y) res+=query(rs,x,y);
	return res;
}
void write(int k,int l,int r){
	if(l==r) return ;
	pushdown(k);
	int mid=l+r>>1;
	write(ls);
	write(rs);
}
struct line{
	ll l,r,id;
}A[N];
bool cmp(line x,line y){
	return x.r<y.r;
}
int main(){
	scanf("%lld%lld",&n,&q);
	pre(1,1,n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=q;i++)
		scanf("%lld%lld",&A[i].l,&A[i].r),A[i].id=i;
	sort(A+1,A+q+1,cmp);
	for(int i=1,to=0;i<=q;i++){
		while(to<A[i].r){
			to++;
			while(top1&&a[stak1[top1]]>=a[to])
				top1--;
			change(1,1,n,stak1[top1]+1,to,(tag){a[to],0,0,0,0,0});
			stak1[++top1]=to;
			change(1,1,n,1,to,(tag){0,0,0,0,1,0});
		}
		ans[A[i].id]=query(1,1,n,A[i].l,A[i].r);
	}
	for(int i=1;i<=q;i++)
		printf("%lld\n",ans[i]);
	return 0;
}