#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 2e5+5;
const string NAME = "";
int n,q,a[MAXN];
ll rs[MAXN];
vector<pair<int,int>> upd[MAXN];
vector<pair<pair<int,int>,int>> query[MAXN];
int L[MAXN],R[MAXN],cntL[MAXN],cntR[MAXN];
void build1(){
stack<int> st;
for(int i = 1; i<=n; ++i){
while(!st.empty()&&a[i]>=a[st.top()]) st.pop();
L[i]=(st.empty() ? 0 : st.top())+1;
cntL[i]=i-L[i];
st.ins(i);
}
while(!st.empty()) st.pop();
for(int i = n; i>0; --i){
while(!st.empty()&&a[i]>a[st.top()]) st.pop();
R[i]=(st.empty() ? n+1 : st.top())-1;
cntR[i]=(R[i]-i);
st.ins(i);
}
}
int st[20][MAXN];
void build2(){
for(int i = 1; i<=n; ++i)
st[0][i]=i;
for(int i = 1; i<=__lg(n); ++i)
for(int j = 1; j+(1<<i)-1<=n; ++j){
if(a[st[i-1][j]]>a[st[i-1][j+(1<<(i-1))]]) st[i][j]=st[i-1][j];
else st[i][j]=st[i-1][j+(1<<(i-1))];
}
}
int rmq(int l, int r){
int k=__lg(r-l+1);
if(a[st[k][l]]>a[st[k][r-(1<<k)+1]]) return st[k][l];
return st[k][r-(1<<k)+1];
}
array<ll,3> sgt[MAXN<<2];
void build(int id, int l, int r){
if(l==r) return sgt[id][0]=a[l], void();
int mid=(l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
for(int i = 0; i<3; ++i)
sgt[id][i]=sgt[id<<1][i]+sgt[id<<1|1][i];
}
void update(int id, int l, int r, int pos, int type){
if(pos<l||r<pos) return;
if(l==r){
if(type==0) sgt[id][0]=0, sgt[id][1]=1ll*(min(cntL[l],cntR[l])+1)*a[l], sgt[id][2]=0;
else if(type==1) sgt[id][0]=0, sgt[id][1]=1ll*(cntL[l]+cntR[l]+1)*a[l], sgt[id][2]=a[l];
else if(type==2) sgt[id][0]=sgt[id][1]=sgt[id][2]=0;
return;
}
int mid=(l+r)>>1;
update(id<<1,l,mid,pos,type);
update(id<<1|1,mid+1,r,pos,type);
for(int i = 0; i<3; ++i)
sgt[id][i]=sgt[id<<1][i]+sgt[id<<1|1][i];
}
array<ll,3> get(int id, int l, int r, int u, int v){
if(v<l||r<u) return {0,0,0};
if(u<=l&&r<=v) return sgt[id];
int mid=(l+r)>>1;
array<ll,3> L=get(id<<1,l,mid,u,v), R=get(id<<1|1,mid+1,r,u,v);
return {L[0]+R[0],L[1]+R[1],L[2]+R[2]};
}
int main()
{
tt;
if(fopen((NAME + ".INP").c_str(), "r")) fo;
cin >> n >> q;
for(int i = 1; i<=n; ++i)
cin >> a[i];
build1();
build2();
for(int i = 1; i<=q; ++i){
int k,l,r;
cin >> k >> l >> r;
int pos=rmq(max(1,l-k),l);
int rpos=min({R[pos],r,pos+k});
rs[i]+=1ll*a[pos]*(rpos-l+1), l=pos+1;
if(rpos==r) continue;
pos=rmq(max(1,r-k),r);
int lpos=max(pos,rpos+1);
rs[i]+=1ll*a[pos]*(r-lpos+1), r=pos-1;
if(lpos==rpos+1) continue;
query[k].pb(mp(l,r),i);
}
for(int i = 1; i<=n; ++i){
if(cntL[i]==i-1) cntL[i]=1e9;
if(cntR[i]==n-i) cntR[i]=1e9;
if(min(cntL[i],cntR[i])==1e9) continue;
upd[min(cntL[i],cntR[i])].pb(0,i);
if(max(cntL[i],cntR[i])==1e9) continue;
upd[max(cntL[i],cntR[i])].pb(1,i);
upd[cntL[i]+cntR[i]].pb(2,i);
}
build(1,1,n);
for(int k = 0; k<=n; ++k){
for(pair<pair<int,int>,int>& p : query[k]){
array<ll,3> sum=get(1,1,n,p.fi.fi,p.fi.se);
rs[p.se]+=(k+1)*sum[0]+sum[1]-k*sum[2];
}
for(pair<int,int>& p : upd[k])
update(1,1,n,p.se,p.fi);
}
for(int i = 1; i<=q; ++i)
cout << rs[i] << "\n";
}
