#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,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(int x,int d)
{
	if (x==n+1) return n+1;
	for (int i=x+1;i<=n;++i)
		if (a[i]>d)
			return i;
	return n+1;
}
int main()
{
	int l,r,d;
	n=read(),q=read();
	for (int i=1;i<=n;++i) a[i]=read();
	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,dque[top-1]-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;
}