#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;

ifstream in("nrsubsecv.in");
ofstream out("nrsubsecv.out");

struct el {
	int val, poz;
};

const int N = 1000010;

int n,m/*,poz,aint[3*N],poz1,poz2,piv,aib[N],aibr[N]*/,s[N],nrs,poz[N],eld[N],els[N],smax;
long long nr[N];
el x[N];

inline bool cmp(const el &a, const el &b) {
	if(a.val == b.val)
		return a.poz<b.poz;
	return a.val<b.val;
}
/*
void update(const int &nod, const int &pozx, const int &pozy) {
	if(pozx == pozy) {
		aint[nod] = 1;
		return;
	}
	
	int mi = (pozx + pozy)>>1;
	
	if(poz<=mi)
		update(2*nod, pozx, mi);
	else
		update(2*nod + 1, mi + 1, pozy);
	
	aint[nod] = aint[2*nod] | aint[2*nod + 1];
}

void q1(const int &nod, const int &pozx, const int &pozy) {
	if(poz1)
		return;
	if(pozx == pozy) {
		if(pozx!=piv)
			poz1 = pozx;
		return;
	}
	
	int mi = (pozx + pozy)>>1;
	
	if(mi<piv-1 && aint[2*nod + 1])
		q1(2*nod + 1, mi + 1, pozy);
	if(aint[2*nod])
		q1(2*nod, pozx, mi);
}

void q2(const int &nod, const int &pozx, const int &pozy) {
	if(!aint[nod] || poz2)
		return;
	if(pozx == pozy) {
		if(pozx!=piv)
			poz2 = pozx;
		return;
	}
	
	int mi = (pozx + pozy)>>1;
	
	if(mi>piv && aint[2*nod])
		q2(2*nod, pozx, mi);
	if(aint[2*nod] + 1)
		q2(2*nod + 1, mi + 1, pozy);
}

void update(int poz) {
	
	for(;poz<=n;poz += poz & (-poz))
		aib[poz] += 1;
}

inline int sum(int poz) {
	int s = 0;
	for(;poz!=0; poz -= poz & (-poz))
		s+=aib[poz];
	return s;
}

inline int q(const int &pozx, const int &pozy) {
	return sum(pozy) - sum(pozx-1);
}*/

int main() {
	int i,a,b,pas,j,j2;
	
	in >> n >> m;
	
	for(i = 1; i<=n; ++i)
		{in >> x[i].val, x[i].poz = i; if(x[i].val>smax) smax = x[i].val;}
	
	/*sort(x + 1, x + n + 1, cmp);
	
	for(i = 1; i<=n; ++i) {
		
		poz1 = 0; poz2 = 0; piv = x[i].poz;
		q1(1,1,n);
		
		q2(1,1,n);
		
		if(poz2 == 0)
			poz2 = n+1;
		
		pas = 1<<19;
		
		for(j = 0; pas!=0; pas>>=1)
			if(j + pas < x[i].poz && q(x[i].poz - j - pas, x[i].poz)==0)
				j+=pas;
		
		pas = 1<<19;
		for(j2 = 0; pas!=0; pas>>=1)
			if(j2 + pas <= n - x[i].poz && q(x[i].poz, x[i].poz + j2 + pas)==0)
				j2+=pas;
		
		nr[x[i].val] += (long long)(j + 1)*(j2 + 1);
		
		update(x[i].poz);
		//poz = x[i].poz;
		//update(1,1,n);
	}*/
	
	for(i = 1; i<=n; ++i) {
		while(nrs!=0 && x[s[nrs]].val>=x[i].val)
			--nrs;
		
		s[++nrs] = i;
		els[i] = i - s[nrs - 1];
	}
	
	nrs = 0; s[0] = n+1;
	for(i = n; i!=0; --i) {
		while(nrs!=0 && x[s[nrs]].val>x[i].val)
			--nrs;
		
		s[++nrs] = i;
		eld[i] = s[nrs - 1] - i;
	}
	
	for(i = 1; i<=n; ++i)
		nr[x[i].val] += (long long)els[i] * eld[i];
	
	for(i = 1; i <= smax; ++i)
		nr[i] += nr[i-1];
	
	for(i = 1; i<=m; ++i) {
		in >> a >> b;
		
		out << nr[b] - nr[a-1] << "\n";
	}
	
	return 0;
}