#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int inf=1e9+7,k = 2e5+5;
const int mxn=5e5+5;
struct fen{
ll fw[mxn];
void add(int i,ll amt){i+=k;
for(;i<mxn;i+=i&-i)fw[i]+=amt;
}
ll qr(int i,ll rs=0){i+=k;
for(;i;i-=i&-i)rs+=fw[i];
return rs;
}
}fw[20];
ll a[mxn],l[mxn],r[mxn],sm=0,rs[mxn]{0};
vector<pii>g[mxn],qr[mxn];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n,q;cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
stack<int>st;
for(int i=1;i<=n;i++){
while(!st.empty()&&a[st.top()]<a[i])st.pop();
if(!st.empty())l[i]=st.top();st.push(i);
}while(!st.empty())st.pop();
for(int i=n;i>=1;i--){
while(!st.empty()&&a[st.top()]<=a[i])st.pop();
if(!st.empty())r[i]=st.top();
else r[i]=n+1;
st.push(i);
}
for(int i=1;i<=q;i++){
int l,r,t;cin>>t>>l>>r;
qr[l-1].pb({-i,t});
qr[r].pb({i,t});
}
for(int i=1;i<=n;i++)g[i].pb({1,i}),g[r[i]].pb({2,i});
for(int j=1;j<=n;j++){
sm+=a[j];
for(auto [u,i] : g[j]){
if(u==1){
//if(i!=3)continue;
fw[0].add(-i,-a[i]);
fw[1].add(-i,a[i]);
fw[2].add(-i,-i*a[i]);
if(l[i]!=0)fw[3].add(i-l[i],(i-l[i])*a[i]);
if(l[i]!=0)fw[4].add(i-l[i],-a[i]);
if(l[i]!=0)fw[5].add(-l[i],a[i]);
if(l[i]!=0)fw[6].add(-l[i],l[i]*a[i]);
}
if(u==2){
//if(i!=3)continue;
fw[0].add(-i,a[i]);
fw[1].add(-i,-a[i]);
fw[2].add(-i,i*a[i]);
if(l[i]!=0)fw[5].add(-l[i],-a[i]);
if(l[i]!=0)fw[6].add(-l[i],-l[i]*a[i]);
fw[7].add(r[i]-i,-a[i]);
fw[8].add(r[i]-i,r[i]*a[i]);
fw[9].add(r[i]-i,-i*a[i]);
if(l[i]!=0)fw[10].add(r[i]-l[i],-r[i]*a[i]);
if(l[i]!=0)fw[11].add(r[i]-l[i],l[i]*a[i]);
if(l[i]!=0)fw[12].add(r[i]-l[i],a[i]);
}
}
for(auto [i,t] : qr[j]){
ll x = (i<0?-1:1);
i=abs(i);
if(j!=0)rs[i]+=sm*(t+1)+(t+1)*fw[0].qr(t-j)+(j+1)*fw[1].qr(t-j)+fw[2].qr(t-j);//(t+1)x or (j+1-i)x for non r[i]
if(j!=0)rs[i]+=fw[3].qr(t)+(t+1)*fw[4].qr(t);//(j-l[i]-t)x or (i-l[i])x
if(j!=0)rs[i]+=(t-j)*fw[5].qr(t-j)+fw[6].qr(t-j);// (j-l[i]-t)x=>0 for non r[i]
if(j!=0)rs[i]+=(t+1)*fw[7].qr(t)+fw[8].qr(t)+fw[9].qr(t);
if(j!=0)rs[i]+=fw[10].qr(t)+fw[11].qr(t)+(t+1)*fw[12].qr(t);
rs[i]*=x;
}
}for(int i=1;i<=q;i++)cout<<rs[i]<<'\n';
}
