#include<iostream>
#include<cstdio>
#include<vector>
#define N 1000000
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct reads
{
	int num,data;
};
struct rds
{
	int l,r;
};
vector<reads>p[N+1];
vector<int>v[N+1];
vector<rds>st[N+1];
int n,q,ST[N+1][21],lg[N+1],c[N+1],c2[N+1],a[N+1],nt[N+1],dque[N+1],top,ans[N+1];
long long c3[N+1];
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int d)
{
	for (;x<=n;x+=lowbit(x)) c[x]+=d;
	return;
}
int query(int x)
{
	int res=0;
	for (;x>=1;x-=lowbit(x)) res+=c[x];
	return res;
}
void add2(int x,int d)
{
	int d2=x*d;
	for (;x<=n;x+=lowbit(x)) c2[x]+=d,c3[x]+=d2;
	return;
}
long long query2(int x)
{
	int d=x+1;
	long long res=0;
	for (;x>=1;x-=lowbit(x)) res+=1ll*c2[x]*d-c3[x];
	return res;
}
void adder(int l,int r,int d)
{
	add2(l,d),add2(r+1,-d);
	return;
}
int get_minn(int l,int r)
{
	int lw=lg[r-l+1];
	return min(ST[l][lw],ST[r-(1<<lw)+1][lw]);
}
int get(int x,int d)
{
	if (x==n+1) return n+1;
	int y=x+1;
	for (int i=lg[n-x+1];i>=0;--i)
		if (y+(1<<i)<=n&&get_minn(x+1,y+(1<<i))<=d)
			y+=(1<<i);
	return y+1;
}
int main()
{
	int l,r,d;
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
	n=read(),q=read();
	for (int i=1;i<=n;++i) ST[i][0]=a[i]=read();
	for (int i=1;i<=lg[n];++i)
		for (int j=1;j+(1<<i)-1<=n;++j)
			ST[j][i]=min(ST[j][i-1],ST[j+(1<<(i-1))][i-1]);
	for (int i=1;i<=q;++i) l=read(),r=read(),p[l].push_back((reads){i,r});
	dque[top=0]=n+1;
	for (int i=n;i>=1;--i)
	{
		while (top&&a[dque[top]]>a[i])
		{
			for (int j=0;j<v[top].size();++j) add(v[top][j],-1);
			for (int j=0;j<st[top].size();++j) adder(st[top][j].l,st[top][j].r,-1);
			top--;
		}
		if (top&&a[dque[top]]==a[i])
		{
			d=dque[top],dque[top]=i,v[top].push_back(get(v[top].back(),a[i])),add(v[top].back(),1);
			if (i+1<=d-1) adder(i+1,d-1,1),st[top].push_back((rds){i+1,d-1});
		}
		else
		{
			dque[++top]=i,v[top]={get(dque[top-1]-1,a[i])},add(v[top].back(),1),st[top].clear();
			if (i+1<=dque[top-1]-1) adder(i+1,dque[top-1]-1,1),st[top].push_back((rds){i+1,dque[top-1]-1});
		}
		for (int j=0;j<p[i].size();++j) ans[p[i][j].num]=query(p[i][j].data)+query2(p[i][j].data);
	}
	for (int i=1;i<=q;++i) printf("%d\n",ans[i]);
	return 0;
}