#include <bits/stdc++.h>
using namespace std;
const int MN = 4e5 + 5;
struct Query {
int id,l,r;
};
long long ans[MN];
struct withT {
long long bit[MN], bit2[MN];
void update (int a, int mult) {
for (int i = max(1,mult); i < MN; i += i & -i) {
bit[i] += mult * 1LL * a;
bit2[i] += a;
}
}
array<long long,2> query (int l, int r) {
long long ret = 0, ret2 = 0;
for (int i = r; i>0; i ^= i & -i) {
ret += bit[i];
ret2 += bit2[i];
}
for (int i = l-1; i>0; i ^= i & -i) {
ret -= bit[i];
ret2 -= bit2[i];
}
return {ret,ret2};
}
} rT, lT;
struct noT {
long long bit[MN];
void update (int i, long long v) {
for (;i<MN;i+=i&-i)
bit[i] += v;
}
long long query (int l, int r) {
long long ret = 0;
for (;r;r^=r&-r)
ret += bit[r];
for (--l;l>0;l^=l&-l)
ret -= bit[l];
return ret;
}
} rNoT, lNoT;
int main() {
int n,q;
scanf ("%d %d",&n,&q);
vector<int> a(n+1), nxt(n+1), lst(n+1), stk;
vector<vector<int>> die(n+2), ch1(n+2), ch2(n+2);
for (int i = 1; i <= n; i++) {
scanf ("%d",&a[i]);
while (!stk.empty() && a[stk.back()] < a[i])
stk.pop_back();
lst[i] = stk.empty() ? -1e9 : stk.back();
stk.push_back(i);
}
stk.clear();
for (int i = n; i >= 1; i--) {
while (!stk.empty() && a[stk.back()] <= a[i])
stk.pop_back();
nxt[i] = stk.empty() ? 1e9 : stk.back();
int ded = min(n+1,min(nxt[i],n+1) - lst[i] - 1);
die[ded].push_back(i);
ch1[min(ded,nxt[i] - i - 1)].push_back(i);
ch2[min(ded,i - lst[i] - 1)].push_back(i);
stk.push_back(i);
}
vector<vector<Query>> queries(n+1);
for (int i = 0; i < q; i++) {
int t,l,r;
scanf ("%d %d %d",&t,&l,&r);
queries[t].push_back({i,l,r});
}
set<pair<int,int>> slT,slNoT,srT,srNoT;
for (int t = n; t >= 1; t--) {
for (int i : die[t+1]) { //revival
srNoT.insert({nxt[i],a[i]});
rNoT.update(nxt[i],a[i] * 1LL * nxt[i]);
slT.insert({lst[i] + 1,a[i]});
lT.update(a[i],lst[i] + 1);
}
for (int i : ch1[t+1]) { //rNoT --> rT
rNoT.update(nxt[i],-a[i] * 1LL * nxt[i]);
srNoT.erase({nxt[i],a[i]});
rT.update(a[i],i+1);
srT.insert({i+1,a[i]});
}
for (int i : ch2[t+1]) { //lT --> lNoT
lT.update(-a[i],lst[i] + 1);
slT.erase({lst[i] + 1,a[i]});
lNoT.update(i,a[i] * 1LL * i);
slNoT.insert({i,a[i]});
}
for (auto &[idx,l,r] : queries[t]) {
auto [r1,r2] = rT.query(l-t+1,r-t);
auto [l1,l2] = lT.query(l-t,r-t);
long long sum = rNoT.query(l+1,r) + r1 + r2 * t - lNoT.query(l,r) - l1 - l2 * t;
{
pair<int,int> mxL = {0,0};
auto it = slNoT.upper_bound(pair(l,(int)1e9));
if (it != slNoT.begin()) mxL = *prev(it);
it = slT.upper_bound(pair(l-t,(int)1e9));
if (it != slT.begin()) mxL = max(mxL,pair(prev(it)->first+t,prev(it)->second));
if (mxL.first != l) sum -= (long long)mxL.second * l;
}
{
pair<int,int> nxtR = {n+5,n+5};
auto it = srNoT.upper_bound(pair(r,(int)1e9));
if (it != srNoT.end()) nxtR = *it;
it = srT.upper_bound(pair(r-t,(int)1e9));
if (it != srT.end()) {
nxtR = min(nxtR,pair(min(it->first+t,n+1),it->second));
}
sum += (long long)nxtR.second * (r+1);
}
ans[idx] = sum;
}
}
for (int i = 0; i < q; i++) printf ("%lld\n",ans[i]);
return 0;
}
