// Problem: P8078 [WC2022] 秃子酋长
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8078
// Memory Limit: 512 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// 私は猫です

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
#define SZ(x) ((int)x.size())
using namespace std;
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=998244353,maxn=2000005;
ll ans[maxn];
int a[maxn],n,p[maxn],zsy;
namespace DS{
	ll t[maxn];
	inline void add(int x,ll y){ for(;x<=n;x+=lowbit(x))t[x]+=y; }
	inline ll query(int x){ ll res=0;for(;x;x&=(x-1))res+=t[x]; return res; }
}
basic_string<int>que[maxn];
int pre[maxn],nxt[maxn],to[maxn],ql[maxn],qr[maxn];
inline int calc(int x,int y){
	if(x<=0||x>n||y<=0||y>n)return 0;
	return x>=y?x-y:y-x;
}
void Solve(int l,int r,basic_string<int>&qu){
	if(l==r)return;
	basic_string<int>lef,rig,vec;
	const int mid=(l+r)>>1;
	for(int &i:qu)
		if(qr[i]<=mid)lef+=i;
		else if(mid<ql[i])rig+=i;
		else vec+=i;
	Solve(l,mid,lef),Solve(mid+1,r,rig);
	if(qu.empty())return inplace_merge(p+l,p+mid+1,p+r+1,[&](int x,int y){ return a[x]<a[y]; }),void();
	auto sol_points_only_in_Left=[&](){
		for(const int &i:vec)que[ql[i]]+=i;
		ll sum=0;
		auto upd=[&](int x,int op){
			const auto &y=nxt[x];
			if(!x){
				if(y<=n)DS::add(to[x],-op*y);
			}else if(y==n+1)DS::add(to[x],-op*x);
			else sum+=abs(x-y)*op,DS::add(to[x],op*(-x-y-abs(x-y)));	
		};
		int pos=mid;
		F(i,l-1,mid){
			const int x=(i==l-1)?0:p[i],y=(i==mid)?n+1:p[i+1];
			nxt[x]=y,pre[y]=x,to[x]=n+1;
			for(;pos<r&&a[p[pos+1]]<a[y];++pos)chkmin(to[x],p[pos+1]);
			upd(x,1);
		}
		F(i,l,mid){
			for(int &id:que[i])ans[id]+=sum+DS::query(qr[id]);
			const int x=pre[i],y=nxt[i];
			upd(x,-1),upd(i,-1),chkmin(to[x],to[i]),nxt[x]=y,pre[y]=x,upd(x,1);
			que[i].clear();
		}
	};
	auto sol_points_only_in_Right=[&](){
		for(const int &i:vec)que[qr[i]]+=i;
		ll sum=0;
		auto upd=[&](int x,int op){
			const auto &y=nxt[x];
			if(!x){
				if(y<=n)sum+=op*y,DS::add(to[x]+1,-op*y);
			}else if(y==n+1) sum+=op*x,DS::add(to[x]+1,-op*x);
			else sum+=op*(x+y),DS::add(to[x]+1,op*(abs(x-y)-x-y));
		};
		int pos=l-1;
		F(i,mid,r){
			const int x=(i==mid)?0:p[i],y=(i==r)?n+1:p[i+1];
			nxt[x]=y,pre[y]=x,to[x]=0;
			for(;pos<mid&&a[p[pos+1]]<a[y];++pos)chkmax(to[x],p[pos+1]);
			upd(x,1);
		}
		dF(i,r,mid+1){
			for(const int &id:que[i])ans[id]+=sum+DS::query(ql[id]);
			const int x=pre[i],y=nxt[i];
			upd(x,-1),upd(i,-1),chkmax(to[x],to[i]),nxt[x]=y,pre[y]=x,upd(x,1);
			que[i].clear();
		}
	}; sol_points_only_in_Right(),sol_points_only_in_Left();
    inplace_merge(p+l,p+mid+1,p+r+1,[&](int x,int y){ return a[x]<a[y]; });
}
void solve(){
	cin>>n>>zsy,a[n+1]=n+1,a[0]=0;
	F(i,1,n)cin>>a[i],p[i]=i;
	basic_string<int>U;
	F(i,1,zsy)cin>>ql[i]>>qr[i],U+=i;
	Solve(1,n,U);
	F(i,1,zsy)cout<<ans[i]<<'\n';
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int zsy=1;
	F(____,1,zsy)solve();
}