#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 4e5+10;
struct act{
int l, v;
};
struct seg{
ll s[maxn*4], tg[maxn*4];
void push(int o, int l, int r){
if (tg[o]) {
s[o] += tg[o] * (r-l+1);
if (l!=r) {
tg[o*2] += tg[o];
tg[o*2+1] += tg[o];
}
tg[o] = 0;
}
}
void MO(int L, int R, ll v, int o=1, int l=0, int r=maxn-1) {
push(o,l,r);
if (l>R || r<L) return;
if (l >= L && r <= R) {
tg[o] += v;
push(o,l,r);
return;
}
int mid = (l+r)/2;
MO(L,R,v,o*2,l,mid);
MO(L,R,v,o*2+1,mid+1,r);
s[o] = (s[o*2]+ s[o*2+1]);
}
ll QU(int L, int R, int o=1, int l=0, int r=maxn-1) {
push(o,l,r);
if (l>R || r<L) return 0;
if (l>=L && r<=R) {
return s[o];
}
int mid = (l+r)/2;
return (QU(L,R,o*2,l,mid)+ QU(L,R,o*2+1,mid+1,r));
}
void go(act A) {
MO(max(A.l,0ll), maxn-1, A.v);
}
seg(){
memset(s, 0, sizeof s);
memset(tg, 0, sizeof tg);
}
};
seg straight, slant;
vector<act> straighta[maxn], slanta[maxn];
void Tri(int a, int b, int v) {
if (v == 0) return;
bug("tri", a, b, v);
int steps = b-a+1;
straight.MO(b+1, maxn-1, -v);
slant.MO(a, maxn-1, v);
if (steps < maxn) {
straighta[steps].pb({b+1, +v});
slanta[steps].pb({a, -v});
}
}
int lbig[maxn], rbig[maxn];
int a[maxn];
ll ask(int t, int l, int r) {
ll str = straight.QU(l,r);
ll sla = slant.QU(max(l-t,0ll), max(r-t,0ll));
return str + sla;
}
ll ans[maxn];
struct que{
int t, l, r, id;
};
signed main(){
IOS();
bug(1,2);
int n; cin>>n;
int q; cin>>q;
REP(i,n) {
cin>>a[i];
}
{
vector<pii> yo; yo.pb({-n-2,inf}); // stuff on the left are bigger
REP(i,n) {
while (yo.back().s < a[i]) {
yo.pop_back();
}
lbig[i] = yo.back().f;
yo.pb({i, a[i]});
bug(i, lbig[i]);
}
}
{
vector<pii> yo; yo.pb({n,inf}); // stuff on the left are bigger
RREP(i,n) {
while (yo.back().s <= a[i]) { // leq here
yo.pop_back();
}
rbig[i] = yo.back().f;
yo.pb({i, a[i]});
bug(i, rbig[i]);
}
}
REP(i,n) {
int prv = lbig[i] + 1;
int j = rbig[i] - 1;
Tri(prv, j, a[i]);
Tri(prv, i-1, -a[i]);
Tri(i+1, j, -a[i]);
}
vector<que> bar;
REP(i,q) {
int t,l,r;
cin>>t>>l>>r;
--l; --r;
bar.pb({t,l,r,i});
}
sort(ALL(bar), [&](que a, que b){return a.t < b.t;});
int nat = -1;
for (auto e : bar) {
while (nat < e.t) {
++nat;
bug(nat);
for (act a : straighta[nat]) {
bug("straight", a.l, a.v);
straight.go(a);
}
for (act a : slanta[nat]) {
bug(a.l, a.v);
slant.go(a);
}
}
ans[e.id] = ask(e.t, e.l, e.r);
}
REP(i,q) {
cout<<ans[i]<<endl;
}
}
/*
5 3
5 0 0 0 0
0 1 3
1 1 3
2 1 3
*/
