#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define int ll
#define y1 yy
#define maksim gay
#define ppb pop_back
#define gcd(a,b) __gcd(a,b)
#define in insert
const int dx[4]={-1,0,1,0};
const int dy[4]={0,-1,0,1};
const int inf=1e16;
const int N=5e4+100;
const int MAX=4e5+10;
const int mod=1e9+7;
int n,q;
int a[MAX];
int l[MAX],r[MAX];
int ans[MAX];
vector<pair<pii,int>> zap[MAX];
vector<pair<pii,int>> ev_diag[MAX],ev_norm[MAX];
struct segtree{
int t[4*MAX];
int add[4*MAX];
segtree(){
mem(t,0);
mem(add,0);
}
void push(int v,int tl,int tr){
int tm=(tl+tr);
if(tm>=0)tm/=2;
else{
tm=tm/2;
tm--;
}
add[2*v]+=add[v];
add[2*v+1]+=add[v];
t[2*v]+=add[v]*(tm-tl+1);
t[2*v+1]+=add[v]*(tr-tm);
add[v]=0;
}
void update(int v,int tl,int tr,int l,int r,int x){
// if(v>1000)return;
if(l>r||tl>r||l>tr)return;
if(l<=tl&&tr<=r){
t[v]+=x*(tr-tl+1);
add[v]+=x;
return;
}
push(v,tl,tr);
int tm=(tl+tr);
if(tm>=0)tm/=2;
else{
tm=tm/2;
tm--;
}
update(2*v,tl,tm,l,r,x);
update(2*v+1,tm+1,tr,l,r,x);
t[v]=t[2*v]+t[2*v+1];
}
int get(int v,int tl,int tr,int l,int r){
if(l>r||tl>r||l>tr)return 0;
if(l<=tl&&tr<=r)return t[v];
push(v,tl,tr);
int tm=(tl+tr);
if(tm>=0)tm/=2;
else{
tm=tm/2;
tm--;
}
return get(2*v,tl,tm,l,r)+get(2*v+1,tm+1,tr,l,r);
}
}t[2];
void upd_triangle(int lx,int ly,int rx,int ry,int x){
int lef_diag=lx-ly;
int rig_diag=rx-ly;
// cout<<lx<<" "<<rx<<" "<<ly<<" "<<ry<<" "<<x<<" "<<lef_diag<<" "<<rig_diag<<"\n";
ev_diag[ly].pb({{lef_diag,rig_diag},x});
ev_diag[ry+1].pb({{lef_diag,rig_diag},-x});
}
void upd_square(int lx,int ly,int rx,int ry,int x){
// cout<<lx<<" "<<rx<<" "<<ly<<" "<<ry<<" "<<x<<"\n";
ev_norm[ly].pb({{lx,rx},x});
ev_norm[ry+1].pb({{lx,rx},-x});
}
void upd_triangle(int l,int r,int x){
// cout<<l<<" "<<r<<" "<<x<<"\n";
int h=r-l;
upd_triangle(l,0,n,n-l,x);
if(r!=n)upd_triangle(r+1,h+1,n,n-l,-x);
if(r!=n)upd_square(r+1,0,n,h,-x);
}
void solve(){
cin>>n>>q;
stack<int> st;
for(int i=1;i<=n;i++)cin>>a[i];
l[1]=0;
st.push(1);
for(int i=2;i<=n;i++){
l[i]=i-1;
while(!st.empty()&&a[st.top()]<=a[i]){
l[i]=l[st.top()];
st.pop();
}
st.push(i);
}
r[n]=n+1;
for(int i=n-1;i>=1;i--){
r[i]=i+1;
while(!st.empty()&&a[st.top()]<a[i]){
r[i]=r[st.top()];
st.pop();
}
st.push(i);
}
for(int i=1;i<=q;i++){
int t,l,r;
cin>>t>>l>>r;
zap[t].pb({{l,r},i});
}
for(int i=1;i<=n;i++){
if(l[i]==0)l[i]=i-n-1;
int tl=l[i]+1;
int tr=r[i]-1;
if(tl>tr)continue;
upd_triangle(tl,i-1,-a[i]);
upd_triangle(i+1,tr,-a[i]);
upd_triangle(tl,tr,a[i]);
}
for(int i=0;i<=n;i++){
for(auto x:ev_diag[i]){
int l=x.F.F,r=x.F.S;
// cout<<l<<" "<<r<<" "<<x.S<<"\n";
t[1].update(1,-n,n,l,r,x.S);
}
for(auto x:ev_norm[i]){
int l=x.F.F,r=x.F.S;
t[0].update(1,0,n,l,r,x.S);
}
for(auto x:zap[i]){
int lef_diag=x.F.F-i;
int rig_diag=x.F.S-i;
int lef_norm=x.F.F;
int rig_norm=x.F.S;
// cout<<t[1].get(1,-n,n,lef_diag,rig_diag)<<"\n";
ans[x.S]=t[0].get(1,0,n,lef_norm,rig_norm)+t[1].get(1,-n,n,lef_diag,rig_diag);
}
}
for(int i=1;i<=q;i++){
cout<<ans[i]<<" ";
}
}
main(){
// freopen("prizes.in", "r", stdin);
// freopen("prizes.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
}
}
