#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
struct Seg{
int n,t=0;
vector<ll>sum,tree;
vector<ll>done;
void init(int N){
n=N;
sum.resize(n<<2,0);
tree.resize(n<<2,0);
done.resize(n<<2,0);
}
void push(int node){
tree[node]+=sum[node]*(t-done[node]);
done[node]=t;
}
int l,r;
void update(int tar,ll val,ll kat){
int node=1,left=0,right=n-1;
while(left<right){
push(node);
tree[node]+=kat*val;
sum[node]+=val;
node*=2;
if(tar>mid){
node++;
left=mid+1;
}
else right=mid;
}
push(node);
tree[node]+=kat*val;
sum[node]+=val;
}
ll qu(bool type,int node=1,int left=0,int right=-1){
if(right==-1)right=n-1;
if(left>r||right<l)return 0;
if(!type)push(node);
if(left>=l&&right<=r)return type?sum[node]:tree[node];
return qu(type,node*2,left,mid)+qu(type,node*2+1,mid+1,right);
}
ll query(int left,int right){
l=left;r=right;
if(l>r)return 0;
return qu(false);
}
ll top(int left,int right){
l=left;r=right;
if(l>r)return 0;
return qu(true);
}
};
int n,q;
int arr[200023],nex[200023];
ll pref[200023];
vector<pair<pair<int,int>,ll>>laser;
vector<int>act[200023];
pair<int,pair<int,int>>plan[200023];
int per[200023];
ll ans[200023];
int main(){
ios_base::sync_with_stdio(23^23);cin.tie(NULL);
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>arr[i];
pref[i]=pref[i-1]+arr[i];
}
arr[n+1]=1e9+1;
for(int i=1;i<=q;i++){
int t,l,r;cin>>t>>l>>r;
plan[i]={t,{l,r}};
per[i]=i;
}
sort(per+1,per+q+1,[&](const int &x,const int &y){
return plan[x].fr<plan[y].fr;
});
vector<int>sta={n+1};
for(int i=n;i>=1;i--){
while(arr[sta.back()]<=arr[i])sta.pop_back();
nex[i]=sta.back();
sta.pb(i);
}
sta.clear();
for(int i=1;i<=n;i++){
while(sta.size()&&arr[sta.back()]<arr[i])sta.pop_back();
if(sta.size()&&arr[sta.back()]==arr[i]){
sta.pb(i);
continue;
}
if(sta.size()){
laser.pb({{i,i-sta.back()},arr[sta.back()]-arr[i]});
laser.pb({{nex[i],nex[i]-sta.back()},arr[i]-arr[sta.back()]});
}
sta.pb(i);
}
sort(laser.begin(),laser.end(),[&](const pair<pair<int,int>,ll>&x,const pair<pair<int,int>,ll>&y){
return x.fr.fr-x.fr.sc<y.fr.fr-y.fr.sc;
});
int m=laser.size();
for(int i=0;i<m;i++){
act[laser[i].fr.sc].pb(i);
}
Seg seg,ye;
seg.init(m);
ye.init(n+2);
int p=1;
for(int tim=0;p<=q;tim++){
for(int x:act[tim]){
seg.update(x,laser[x].sc,laser[x].fr.fr);
ye.update(laser[x].fr.fr-1,-laser[x].sc,laser[x].fr.fr-1);
}
while(p<=q&&plan[per[p]].fr==tim){
ll &res=ans[per[p]];
ll left=plan[per[p]].sc.fr,right=plan[per[p]].sc.sc;
res=pref[right]-pref[left-1];
res+=ye.top(1,left-1)*(left-1)+ye.top(right+1,n)*(right);
res+=ye.query(left,right);
int le,ri;
int l=0,r=m;
while(l<r){
int mi=(l+r)/2;
if(laser[mi].fr.fr-laser[mi].fr.sc+tim>=left)r=mi;
else l=mi+1;
}
le=l;
l=-1;r=m-1;
while(l<r){
int mi=(l+r+1)/2;
if(laser[mi].fr.fr-laser[mi].fr.sc+tim<=right)l=mi;
else r=mi-1;
}
ri=l;
res+=seg.top(0,le-1)*(left-1)+seg.top(ri+1,m-1)*right;
res+=seg.query(le,ri);
p++;
}
seg.t++;
}
for(int i=1;i<=q;i++){
cout<<ans[i]<<endl;
}
}
