ref
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
int n, q, a[100005], l[100005], r[100005], sta[100005], din, blc, bel[100005], st[100005][19], mii[17], mlg[100005];
ll sl[100005], sr[100005], now, ans[100005];
struct Ques{
int ll, rr, id;
}qu[100005];
bool cmp(Ques x, Ques y){
if(bel[x.ll]!=bel[y.ll]) return bel[x.ll]<bel[y.ll];
if(bel[x.ll]&1) return x.rr<y.rr;
return x.rr>y.rr;
}
int getPos(int x, int y){
int l=mlg[y-x+1], k=y+1-mii[l];
return a[st[x][l]]<a[st[k][l]]?st[x][l]:st[k][l];
}
ll calL(int x, int y){
int p=getPos(x, y);
return (ll)a[p]*(y-p+1)+sr[x]-sr[p];
}
ll calR(int x, int y){
int p=getPos(x, y);
return (ll)a[p]*(p-x+1)+sl[y]-sl[p];
}
int main(){//freopen("sequence9.in", "r", stdin);
cin>>n>>q;
blc = sqrt(n);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
bel[i] = (i - 1) / blc + 1;
st[i][0] = i;
}
for(int i=1; i<=q; i++){
scanf("%d %d", &qu[i].ll, &qu[i].rr);
qu[i].id = i;
}
sort(qu+1, qu+1+q, cmp);
for(int i=1; i<=n; i++){
while(din && a[sta[din]]>=a[i]) din--;
if(din) l[i] = sta[din];
sta[++din] = i;
}
din = 0;
for(int i=n; i; i--){
r[i] = n + 1;
while(din && a[sta[din]]>=a[i]) din--;
if(din) r[i] = sta[din];
sta[++din] = i;
}
mii[0] = 1;
for(int i=1; i<=16; i++)
mii[i] = mii[i-1] << 1;
for(int i=2; i<=n; i++)
mlg[i] = mlg[i>>1] + 1;
for(int j=1; j<=16; j++)
for(int i=1; i<=n; i++){
st[i][j] = st[i][j-1];
int k=i+mii[j-1];
if(k<=n) st[i][j] = (a[st[i][j-1]]<a[st[k][j-1]])?st[i][j-1]:st[k][j-1];
}
for(int i=1; i<=n; i++)
sl[i] = sl[l[i]] + (ll)(i - l[i]) * a[i];
for(int i=n; i; i--)
sr[i] = sr[r[i]] + (ll)(r[i] - i) * a[i];
int gtl=qu[1].ll, zzh=gtl-1;
for(int i=1; i<=q; i++){
while(gtl>qu[i].ll) now += calL(--gtl, zzh);
while(zzh<qu[i].rr) now += calR(gtl, ++zzh);
while(gtl<qu[i].ll) now -= calL(gtl++, zzh);
while(zzh>qu[i].rr) now -= calR(gtl, zzh--);
ans[qu[i].id] = now;
}
for(int i=1; i<=q; i++)
printf("%lld
", ans[i]);
return 0;
}