#include <bits/stdc++.h>
/*#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <map>
#include <set>
#include <string>*/
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x, n) memset(x,n,sizeof(x));
#define fi first;
#define se second;
#define pb push_back;
typedef long long ll;
typedef unsigned long long ull;
typedef complex<double> cd;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double eps=1e-8;
const int maxn=1e5+10;
const int mod=2333;
const int inf=0x3f3f3f3f;
const ll INF=0x7f7f7f7f7f7f7f7f;
const double pi=acos(-1.0);
#define CC getchar()
template <typename T>
inline void read(T &s){
    T t=1; char k=CC; s=0;
    for (;k<'0'||k>'9';k=CC) if (k=='-') t=-1;
    for (;k>='0'&&k<='9';k=CC) s=(s<<1)+(s<<3)+(k^48);
    s*=t;
}

ll n,a[maxn],sq,ans[maxn],pre[maxn],fl[maxn],fr[maxn],nw=0,mn[maxn][25];

struct quer{
    ll l,r,no;
}que[maxn];

struct stac{
    ll val,no;
}s[maxn];

bool cmp(quer x,quer y)
{
    if((x.l-1)/sq!=(y.l-1)/sq) return x.l<y.l;
    if(((x.l-1)/sq)%2==1) return x.r>y.r;
    return x.r<y.r;
}

void ST(ll n){//在i到1<<j区间内的最小值的下标 
    for(ll j=1;(1<<j)-1<n;j++)
        for(ll i=1;i+(1<<j)-1<=n;i++)
            if(a[mn[i][j-1]]<=a[mn[i+(1<<j-1)][j-1]]) mn[i][j]=mn[i][j-1];
            else mn[i][j]=mn[i+(1<<j-1)][j-1]; 
}

ll rmq(ll s,ll v){//在区间s->v之间找区间最小值，
    ll k=log2(v-s+1);
    if (a[mn[s][k]]<=a[mn[v-(1<<k)+1][k]])
        return mn[s][k];
    else
        return mn[v-(1<<k)+1][k]; 
}

ll getfl(ll x)
{
    if(fl[x]!=-inf) return fl[x];
    if(pre[x]==0) fl[x]=a[x];
    else fl[x]=a[x]*(x-pre[x])+getfl(pre[x]);
    return fl[x];
}

ll getfr(ll x)
{
    if(fr[x]!=-inf) return fr[x];
    if(pre[x]==n+1) fr[x]=a[x];
    else fr[x]=a[x]*(pre[x]-x)+getfr(pre[x]);
    return fr[x];
}

void init()
{
    ST(n);
    for(ll i=1;i<=n;i++) fr[i]=fl[i]=-inf;
    ll ed=0;
    s[0].no=0;
    for(ll i=1;i<=n;i++)
    {
        while(ed>0&&s[ed].val>=a[i])ed--;
        pre[i]=s[ed].no;
        s[++ed].val=a[i];
        s[ed].no=i;
    }
    for(ll i=n;i>0;i--) getfl(i);
    ed=0;
    s[0].no=n+1;
    for(ll i=n;i>0;i--)
    {
        while(ed>0&&s[ed].val>=a[i]) ed--;
        pre[i]=s[ed].no;
        s[++ed].val=a[i];
        s[ed].no=i;
    }
    for(ll i=1;i<=n;i++) getfr(i);
}

void add(ll l,ll r){
    
    if(l<=r)
    {
        ll t=rmq(l,r);
        nw+=(t-l+1)*a[t]+fl[r]-fl[t];
        
    }
    else
    {
        ll t=rmq(r,l);
        nw+=(l-t+1)*a[t]+fr[r]-fr[t];
    }
}

void del(ll l,ll r)
{
    if(l<=r)
    {
        ll t=rmq(l,r);
        nw-=((t-l+1)*a[t]+fl[r]-fl[t]);
    }
    else
    {
        ll t=rmq(r,l);
        nw-=((l-t+1)*a[t]+fr[r]-fr[t]);
    }
}

int main(){
    ll q;
    scanf("%lld%lld",&n,&q);
    sq=sqrt(n);
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        mn[i][0]=i;
    }
    init();
    for(ll i=1;i<=q;i++)
    {
        scanf("%lld%lld",&que[i].l,&que[i].r);
        que[i].no=i;
    }
    sort(que+1,que+1+q,cmp);
    ll l=1,r=0;
    for(ll i=1;i<=q;i++)
    {
        while(l>que[i].l)  add(r,--l);
        while(r<que[i].r)  add(l,++r);
        while(l<que[i].l)  del(r,l++);     
        while(r>que[i].r)  del(l,r--);     
        ans[que[i].no]=nw;
    }
    for(ll i=1;i<=q;i++) printf("%lld\n",ans[i]);
    return 0;
}