#include <bits/stdc++.h>
#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
using namespace std;
typedef long long ll;
const int MAXN = 200000+5;
const int MAXQ = 200000+5;
struct STree{
ll n;
vector<ll> st;
vector<ll> lazy;
STree(ll n):n(n), st(4*n+5,0) , lazy(4*n+5,0) {}
void push(ll k, ll l, ll r){
if(lazy[k]==0) return;
st[k]+=lazy[k]*(r-l);
if(l+1!=r){
lazy[2*k]+=lazy[k];
lazy[2*k+1]+=lazy[k];
}
lazy[k]=0;
}
void upd(ll k, ll l, ll r, ll L, ll R, ll v){
push(k,l,r);
if(l>=R || r<=L) return;
if(l>=L && r<=R){
lazy[k]+=v;
push(k,l,r);
return;
}
ll mid = (l+r)/2;
upd(2*k,l,mid,L,R,v);
upd(2*k+1,mid,r,L,R,v);
st[k]=st[2*k]+st[2*k+1];
}
ll query(ll k, ll l, ll r, ll L, ll R){
push(k,l,r);
if(l>=R||r<=L) return (ll)0;
if(l>=L && r<=R) return st[k];
ll mid = (l+r)/2;
return query(2*k,l,mid,L,R)+query(2*k+1,mid,r,L,R);
}
void upd(ll p, ll v){ upd(1,0,n,p,n,v); }
ll query(ll l, ll r){ return query(1,0,n,l,r); }
};
struct Update{
ll time;
ll type;
ll pos;
ll val;
Update(ll time = 0, ll type = 0, ll pos = 0, ll val = 0):time(time), type(type), pos(pos), val(val){}
};
bool operator<(const Update &a, const Update &b) {
if(a.time<b.time) return true;
if(a.time>b.time) return false;
return a.type<b.type;
}
struct Query{
ll i;
ll time;
ll left;
ll right;
Query(ll i = 0, ll time = 0, ll left = 0, ll right = 0):i(i), time(time), left(left),right(right) {}
};
bool operator<(const Query &a, const Query &b){
if(a.time<b.time) return true;
if(a.time>b.time) return false;
return a.left<b.left;
}
ll n,q;
ll s[MAXN];
ll t[MAXQ];
ll l[MAXQ];
ll r[MAXQ];
int main(){
cin>>n>>q;
forn(i,0,n) cin>>s[i];
forn(i,0,q) cin>>t[i]>>l[i]>>r[i], l[i]--, r[i]--;
vector<Query> query; forn(i,0,q) query.pb(Query(i,t[i],l[i],r[i]));
sort(ALL(query));
vector<ll> lft(n,-(n+1));
vector<ll> rgt(n,n+1);
vector<ll> aux;
forn(i,0,n){
while(!aux.empty() && s[aux.back()]<=s[i]){
aux.pop_back();
}
lft[i]=(aux.empty()?-(n+1):aux.back());
aux.pb(i);
}
aux.clear();
for(int i = n-1; i>=0; i--){
while(!aux.empty() && s[aux.back()]<s[i]){
aux.pop_back();
}
rgt[i]=(aux.empty()?n+1:aux.back());
aux.pb(i);
}
forn(i,0,n){
//cout<<i<<" ("<<lft[i]<<" "<<rgt[i]<<")"<<'\n';
}
vector<Update> upd;
forn(i,0,n){
//cout<<"Descomposicion "<<i<<'\n';
if(rgt[i]-(lft[i]+1)!=0){ // triangulo general
// diagonal = lft[i]+1
// verical = rgt[i]
upd.pb(Update(0 , 1, lft[i]+1, s[i]));
upd.pb(Update(rgt[i]-(lft[i]+1) , 1, lft[i]+1, -s[i]));
upd.pb(Update(0 , 0, rgt[i] , -s[i]));
upd.pb(Update(rgt[i]-(lft[i]+1) , 0, rgt[i] , s[i]));
//cout<<"general: diagonal( "<<lft[i]+1<<" ) "<<"vertical( "<<rgt[i]<<" )\n";
}
if(i-(lft[i]+1)!=0){ // triangulo superior izq
// diagonal = lft[i]+1
// vertical = i
upd.pb(Update(0 , 1, lft[i]+1, -s[i]));
upd.pb(Update(i-(lft[i]+1) , 1, lft[i]+1, s[i]));
upd.pb(Update(0 , 0, i , s[i]));
upd.pb(Update(i-(lft[i]+1) , 0, i , -s[i]));
//cout<<"sup izq: diagonal( "<<lft[i]+1<<" ) "<<"vertical( "<<i<<" )\n";
}
if(rgt[i]-(i+1)!=0){ // triangulo superior der
// diagonal = i+1
// vertical = rgt[i]
upd.pb(Update(0 , 1, i+1 , -s[i]));
upd.pb(Update(rgt[i]-(i+1) , 1, i+1 , s[i]));
upd.pb(Update(0 , 0, rgt[i] , s[i]));
upd.pb(Update(rgt[i]-(i+1) , 0, rgt[i] , -s[i]));
//cout<<"sup der: diagonal( "<<i+1<<" ) "<<"vertical( "<<rgt[i]<<" )\n";
}
}
sort(ALL(upd));
STree vert(3*n+20);
STree diag(3*n+20);
ll ind = 0;
//cout<<SZ(upd)<<'\n';
vector<ll> res(q);
forn(i,0,SZ(query)){
while(ind<SZ(upd) && upd[ind].time<=query[i].time){
if(upd[ind].type==0){
//cout<<"Nueva vertical "<<upd[ind].pos+(n+10)<<" "<<upd[ind].val<<" time -> "<<upd[ind].time<<'\n';
vert.upd(upd[ind].pos+(n+10) , upd[ind].val);
}else{
//cout<<"Nueva diagonal "<<upd[ind].pos+(n+10)<<" "<<upd[ind].val<<" time -> "<<upd[ind].time<<'\n';
diag.upd(upd[ind].pos+(n+10) , upd[ind].val);
}
/*cout<<"RES: \n";
forn(j,0,3*n+20) cout<<vert.query(j,j+1)<<" "; cout<<'\n';
forn(j,0,3*n+20) cout<<diag.query(j,j+1)<<" "; cout<<'\n'; */
ind++;
}
// cout<<"se responde querie i: "<<i<<" "<<query[i].time<<'\n';
//cout<<"Ve "<<query[i].left+(n+10)<<" "<<query[i].right+(n+10)+1<<'\n';
ll ve = vert.query(query[i].left+(n+10), query[i].right+(n+10)+1);
//cout<<"Di "<<query[i].left+(n+10)-query[i].time<<" "<<query[i].right+(n+10)+1-query[i].time<<'\n';
ll di = diag.query(query[i].left+(n+10)-query[i].time , query[i].right+(n+10)+1-query[i].time);
// cout<<ve<<" "<<di<<'\n';
res[query[i].i]=ve+di;
}
for(auto i:res) cout<<i<<'\n';
return 0;
}
