#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
int N, Q, A[MAXN+10];
ll B[MAXN+10];
struct Data
{
int y, x, p;
};
vector<Data> AV, QV;
ll ans[MAXN+10];
pll tree[MAXN+10];
pll operator + (const pll &p, const pll &q) { return {p.first+q.first, p.second+q.second}; }
void update(int i, pll p) { for(; i<=N; i+=(i&-i)) tree[i]=tree[i]+p; }
pll query(int i) { pll ret={0, 0}; for(; i>0; i-=(i&-i)) ret=ret+tree[i]; return ret; }
int main()
{
scanf("%d%d", &N, &Q);
for(int i=1; i<=N; i++) scanf("%d", &A[i]);
for(int i=1; i<=N; i++) B[i]=B[i-1]+A[i];
for(int i=1; i<=Q; i++)
{
int l, r, t;
scanf("%d%d%d", &t, &l, &r);
ans[i]+=B[r]-B[l-1];
QV.push_back({t, r, i});
QV.push_back({t, l-1, -i});
}
A[N+1]=1e9;
vector<int> S;
for(int i=1; i<=N+1; i++)
{
int bef;
if(!S.empty()) bef=A[S.back()];
while(!S.empty() && A[S.back()]<=A[i])
{
int y1=1, x1=S.back()+1, p=A[S.back()]-bef;
int y2=i-S.back(), x2=i;
AV.push_back({y1, x1, p});
AV.push_back({y2, x2, -p});
bef=A[S.back()];
S.pop_back();
}
if(!S.empty())
{
int y1=1, x1=S.back()+1, p=A[i]-bef;
int y2=i-S.back(), x2=i;
AV.push_back({y1, x1, p});
AV.push_back({y2, x2, -p});
}
S.push_back(i);
}
sort(AV.begin(), AV.end(), [&](const Data &p, const Data &q) { return p.y-p.x<q.y-q.x; });
sort(QV.begin(), QV.end(), [&](const Data &p, const Data &q) { return p.y-p.x<q.y-q.x; });
for(int i=0; i<=N; i++) tree[i]={0, 0};
for(int i=0, j=0; i<QV.size(); i++)
{
for(; j<AV.size() && AV[j].y-AV[j].x<=QV[i].y-QV[i].x; j++)
{
update(AV[j].x, pll(AV[j].p, (ll)AV[j].p*(1-AV[j].x)));
}
pll ret=query(QV[i].x);
if(QV[i].p>0) ans[QV[i].p]+=ret.first*QV[i].x+ret.second;
else ans[-QV[i].p]-=ret.first*QV[i].x+ret.second;
}
reverse(AV.begin(), AV.end());
reverse(QV.begin(), QV.end());
for(int i=0; i<=N; i++) tree[i]={0, 0};
for(int i=0, j=0; i<QV.size(); i++)
{
for(; j<AV.size() && AV[j].y-AV[j].x>=QV[i].y-QV[i].x+1; j++)
{
update(AV[j].y, pll(AV[j].p, (ll)AV[j].p*(1-AV[j].y)));
}
pll ret=query(QV[i].y);
if(QV[i].p>0) ans[QV[i].p]+=ret.first*QV[i].y+ret.second;
else ans[-QV[i].p]-=ret.first*QV[i].y+ret.second;
}
for(int i=1; i<=Q; i++) printf("%lld\n", ans[i]);
}
