#include <bits/stdc++.h>
#define forn(i,n) for(int i=0;i<int(n);++i)
#define fort(i,n) for(int i=0;i<=int(n);++i)
#define fori(i,a,n) for(int i=a;i<int(n);++i)
#define forit(i,a,n) for(int i=a;i<=int(n);++i)
#define ALL(v) v.begin(),v.end()
#define SZ(v) (int)v.size()
#define DBG(a) cerr<<#a<<" = "<<(a)<<endl
#define DBGA(a) cerr<<#a<<" = "<<(a)<<", ";
#define DBG2(a,b) do{DBGA(a)DBG(b);}while(0)
#define DBG3(a,b,c) do{DBGA(a)DBGA(b)DBG(c);}while(0)
#define DBG4(a,b,c,d) do{DBGA(a)DBGA(b)DBGA(c)DBG(d);}while(0)
#define LINE cerr<<"===================================="<<endl
using namespace std;
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
os<<"[";
forn(i,v.size()){
if(i) os<<" ";
os<<v[i];
}
os<<"]";
return os;
}
typedef long long ll;
typedef long double ld;
struct ST{
int n;
vector<ll> st, lz;
ST(int _n){
n = 1<<(32-__builtin_clz(_n-1));
st.resize(2*n-1);
lz.resize(2*n-1);
}
void push(int i, int l, int r){
if(!lz[i]) return;
st[i] += lz[i]*(r-l);
if(i<n-1){
lz[2*i+1] += lz[i];
lz[2*i+2] += lz[i];
}
lz[i] = 0;
}
void update(int ul, int ur, int v, int l, int r, int i){
push(i,l,r);
if(l>=ur||r<=ul) return;
if(l>=ul&&r<=ur){
lz[i] += v;
push(i,l,r);
return;
}
int m=(l+r)/2;
update(ul,ur,v,l,m,2*i+1);
update(ul,ur,v,m,r,2*i+2);
st[i] = st[2*i+1]+st[2*i+2];
}
void update(int l, int v){ // creo que no es necesario r
update(l,n,v,0,n,0);
}
ll query(int ql, int qr, int l, int r, int i){
push(i,l,r);
if(l>=qr||r<=ql) return 0;
if(l>=ql&&r<=qr) return st[i];
int m=(l+r)/2;
return query(ql,qr,l,m,2*i+1)+query(ql,qr,m,r,2*i+2);
}
ll query(int l, int r){
return query(l,r,0,n,0);
}
void print(int l, int r, int i){
push(i,l,r);
if(i >= n-1){
cout<<st[i]<<" ";
return;
}
int m = (l+r)/2;
print(l,m,2*i+1);
print(m,r,2*i+2);
}
void print(){
print(0,n,0);
cout<<"\n";
}
};
struct Update{
int d, t, l, v; // d: diagonal
bool operator<(const Update&o)const{
return t < o.t;
}
};
struct Query{
int i, t, l, r;
bool operator<(const Query&o)const{
return t < o.t;
}
};
void solve(){
int n, q;
cin>>n>>q;
vector<int> s(n);
for(int &x: s) cin>>x;
// procesar todo
vector<int> toLeft(n), toRight(n);
auto comp = [](int a, int b, int i){
if(i == 0) return a < b;
return a <= b;
};
forn(_,2){
stack<int> nge;
forn(i,n){
while(SZ(nge) && comp(s[nge.top()], s[i], _)) nge.pop();
if(SZ(nge)) toLeft[i] = nge.top();
else toLeft[i] = -1;
nge.push(i);
}
reverse(ALL(s));
swap(toLeft, toRight);
}
reverse(ALL(toRight));
for(int &x: toRight) x = n-x-1;
//~ DBG2(toLeft, toRight);
vector<Update> upds;
// calcular updates
const int D = n+2;
auto getTriangle = [&](int i, int h, int v){
if(!h) return;
// diagonal
upds.push_back({1, 0, i+D, +v});
upds.push_back({1, h, i+D, -v});
// vertical
upds.push_back({0, 0, i+D+h, -v});
upds.push_back({0, h, i+D+h, +v});
};
auto getParallelogram = [&](int i){ // obtiene el paralelogramo del i-esimo elemento
int l = toLeft[i] + 1; // aqui empieza su triangulo
if(l == 0) l -= D;
//~ DBG(toLeft[i]);
int r = toRight[i]; // es exclusivo
int h = r - l; // tamaño del triangulo
getTriangle(l,h,s[i]);
getTriangle(l,i-l,-s[i]);
getTriangle(i+1,r-i-1,-s[i]);
};
forn(i,n) getParallelogram(i);
sort(ALL(upds));
// cargar y ordenar queries
vector<Query> qrs(q);
forn(i,q){
int t,l,r;
cin>>t>>l>>r;
--l;
qrs[i] = {i, t, l, r};
}
sort(ALL(qrs));
// responder queries
int j = 0;
ST diag(2*n+5), vert(2*n+5);
vector<ll> ans(q);
for(Query &Q: qrs){
while(j < SZ(upds) && upds[j].t <= Q.t){
Update &U = upds[j];
if(U.d) diag.update(U.l, U.v);
else vert.update(U.l, U.v);
++j;
//~ if(U.v != 0) DBG4(U.d, U.t, U.l, U.v);
//~ if(U.v != 0) diag.print();
//~ if(U.v != 0) vert.print();
}
//~ DBG4("listo para procesar", Q.t, Q.l, Q.r);
ll a = vert.query(Q.l+D, Q.r+D);
ll b = diag.query(Q.l+D-Q.t, Q.r+D-Q.t);
ans[Q.i] = a+b;
}
for(ll x: ans) cout<<x<<"\n";
cerr<<"===============\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL
assert(freopen("input.in", "r", stdin));
//~ freopen("output.out", "w", stdout);
#endif
#ifdef LOCAL
int tcs; cin>>tcs;
while(tcs--)
#endif
solve();
return 0;
}
