#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;

int lg[N],B,f[N][17],pre[N],suf[N],top,s[N];
//pre[i]为第i个数的左边第一个比它小的数的位置
//suf[i]为第i个数的右边第一个比它小的数的位置
ll a[N],sum,fl[N],fr[N],ans[N];

struct node
{
	int l,r,id;
	friend bool operator<(const node a,const node b)
	{
		return (a.l/B!=b.l/B)? a.l<b.l : ((a.l/B)&1) ? a.r<b.r : a.r>b.r;
	}
}q[N];

inline int query(int l,int r)
{
	int k=lg[r-l];
	return a[ f[l][k] ]<a[ f[r-(1<<k)+1][k] ] ? f[l][k] : f[r-(1<<k)+1][k];
}

inline ll left(int l,int r){int p=query(l-1,r);return a[p]*(r-p+1)+fl[l-1]-fl[p];}

inline ll right(int l,int r){int p=query(l,r+1);return a[p]*(p-l+1)+fr[r+1]-fr[p];}

int main()
{
    int n,m;scanf("%d%d",&n,&m);
	B=sqrt(n);
    lg[1]=0;for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
	a[n+1]=a[0]=2e9;

	memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),f[i][0]=i;
	
    for(int j=1;j<=lg[n];j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
        	f[i][j]=query(i,i+(1<<j)-1);

    top=0;
    for(int i=1;i<=n;i++)
    {
        while(top&&a[s[top]]>a[i])suf[s[top--]]=i;
        pre[i]=s[top],s[++top]=i;
    }

    while(top)pre[s[top]]=s[top-1],suf[s[top--]]=n+1;

    for(int i=1;i<=n;i++) fr[i]=a[i]*(i-pre[i])+fr[pre[i]];
    for(int i=n;i>=1;i--) fl[i]=a[i]*(suf[i]-i)+fl[suf[i]];

    for(int i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    sort(q+1,q+m+1);

    for(int i=1,l=q[1].l,r=l-1;i<=m;i++)
    {
        while(l>q[i].l)sum+=left(l,r),l--;
        while(r<q[i].r)sum+=right(l,r),r++;
        while(l<q[i].l)sum-=left(l+1,r),++l;
        while(r>q[i].r)sum-=right(l,r-1),--r;
        ans[q[i].id]=sum;
    }
    for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
    return 0;
}