#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;
int n,q;
struct op {
ll l,r,t,v;
};
void print(op a) {
cout<<a.l<<" "<<a.r<<" "<<a.v<<" "<<a.t<<" ";
}
void tri(int pos,int h,ll v,vector<op> &op1,vector<op> &op2) {
// cout<<pos<<" "<<h<<" tri\n";
op1.push_back({pos+h,2*n+2,h,-v});
// print(op1.back());cout<<"tri1\n";
op2.push_back({pos,2*n+2,h,v});
// print(op2.back());cout<<"tri2\n";
}
void para(int pos,int h,int w,ll v,vector<op> &op1,vector<op> &op2) {
// cout<<pos<<" "<<h<<" "<<w<<" para\n";
if (h>1) tri(pos-h+1,h-1,-v,op1,op2);
if (w>1) tri(pos+1,w-1,-v,op1,op2);
tri(pos-h+1,w+h-1,v,op1,op2);
}
struct SEG {
int n;
vector<ll> tree,lazy;
SEG(int _n):n(_n) {
tree.resize(4*n+10);
lazy.resize(4*n+10);
}
void pd(int l,int r,int id) {
int mid=l+r>>1;
tree[id<<1]+=lazy[id]*(mid-l+1);
lazy[id<<1]+=lazy[id];
tree[id<<1|1]+=lazy[id]*(r-mid);
lazy[id<<1|1]+=lazy[id];
lazy[id]=0;
}
void update(int l,int r,int id,int L,int R,ll val) {
// cout<<l<<" "<<r<<" "<<L<<" "<<R<<" lr LR\n";
if (L<=l and r<=R) {
tree[id]+=val*(r-l+1);
lazy[id]+=val;
return;
}
int mid=l+r>>1;
pd(l,r,id);
if (L<=mid) update(l,mid,id<<1,L,R,val);
if (mid<R) update(mid+1,r,id<<1|1,L,R,val);
tree[id]=tree[id<<1]+tree[id<<1|1];
}
ll query(int l,int r,int id,int L,int R) {
if (L<=l and r<=R) return tree[id];
int mid=l+r>>1;
pd(l,r,id);
ll ans=0;
if (L<=mid) ans+=query(l,mid,id<<1,L,R);
if (mid<R) ans+=query(mid+1,r,id<<1|1,L,R);
return ans;
}
};
int main() {
speed;
cin>>n>>q;
int N=2*n+2;
vector<ll> s(N);
for (int i=1;i<=n;i++) {
cin>>s[i+n+1];
}
vector<op> op1;
vector<op> op2;
vector<ll> lft(N),rt(N);
vector<pll> stk;
for (int i=n+2;i<=2*n+1;i++) {
while (!stk.empty() and stk.back().F<s[i]) stk.pop_back();
if (stk.empty()) lft[i]=n+1;
else lft[i]=i-stk.back().S;
stk.push_back({s[i],i});
// cout<<lft[i]<<" "<<i<<" lft\n";
}
stk.clear();
for (int i=2*n+1;i>=n+2;i--) {
while (!stk.empty() and stk.back().F<=s[i]) stk.pop_back();
if (stk.empty()) rt[i]=2*n+2;
else rt[i]=stk.back().S;
rt[i]-=i;
stk.push_back({s[i],i});
// cout<<rt[i]<<" "<<i<<" rt\n";
}
for (int i=n+2;i<=2*n+1;i++) {
// cout<<i<<" "<<lft[i]<<" "<<rt[i]<<"\n";
para(i,lft[i],rt[i],s[i],op1,op2);
}
vector<op> Q(q);
for (int i=0;i<q;i++) {
ll l,r,t;
cin>>t>>l>>r;
Q[i]={l+n+1,r+n+1,t+1,i};
}
auto cmp=[&](op a,op b) {
return a.t<b.t;
};
sort(all(Q),cmp);
sort(all(op1),cmp);
sort(all(op2),cmp);
SEG s1(N),s2(N);
for (auto OP:op1) {
s1.update(1,N,1,OP.l,OP.r,OP.v);
// cout<<OP.l<<" "<<OP.r<<" "<<OP.t<<" "<<OP.v<<" op1 lrtv\n";
}
for (auto OP:op2) {
s2.update(1,N,1,OP.l,OP.r,OP.v);
// cout<<OP.l<<" "<<OP.r<<" "<<OP.t<<" "<<OP.v<<" op2 lrtv\n";
}
vector<ll> ans(q);
int id1=0,id2=0;
for (int i=0;i<q;i++) {
while (id1<op1.size() and op1[id1].t<Q[i].t) {
s1.update(1,N,1,op1[id1].l,op1[id1].r,-op1[id1].v);
id1++;
}
while (id2<op2.size() and op2[id2].t<Q[i].t) {
s2.update(1,N,1,op2[id2].l,op2[id2].r,-op2[id2].v);
id2++;
}
ans[Q[i].v]=s1.query(1,N,1,Q[i].l,Q[i].r)+s2.query(1,N,1,Q[i].l-Q[i].t+1,Q[i].r-Q[i].t+1);
}
for (int i=0;i<q;i++) {
cout<<ans[i]<<"\n";
}
return 0;
}
/*
5 1
2 4 3 2 1
5 1 5
*/
