#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
struct dat{
ll val=0,lazy=0;
dat(){}
};
struct node{
dat seg[1050000];
ll propo(int u,int s,int e){
if (seg[u].lazy){
seg[u].val+=seg[u].lazy*(e-s+1);
if (s!=e) seg[u<<1].lazy+=seg[u].lazy,seg[u<<1|1].lazy+=seg[u].lazy;
seg[u].lazy=0;
}
return seg[u].val;
}
void update(int i,int j,ll k,int u=1,int s=-200005,int e=200005){
//cerr<<i<<" "<<j<<" "<<k<<" "<<u<<" "<<s<<" "<<e<<endl;
int m=s+e>>1;
if (s==i && e==j){
seg[u].lazy+=k;
}
else{
if (j<=m) update(i,j,k,u<<1,s,m);
else if (m<i) update(i,j,k,u<<1|1,m+1,e);
else update(i,m,k,u<<1,s,m),update(m+1,j,k,u<<1|1,m+1,e);
seg[u].val=propo(u<<1,s,m)+propo(u<<1|1,m+1,e);
}
}
ll query(int i,int j,int u=1,int s=-200005,int e=200005){
propo(u,s,e);
int m=s+e>>1;
if (s==i && e==j) return seg[u].val;
else if (j<=m) return query(i,j,u<<1,s,m);
else if (m<i) return query(i,j,u<<1|1,m+1,e);
else return query(i,m,u<<1,s,m)+query(m+1,j,u<<1|1,m+1,e);
}
}rect=node(),diag=node();
struct upd{
int row;
int s,e;
ll val;
upd(int a,int b,int c,ll d){
row=a,s=b,e=c,val=d;
}
};
struct Q{
int a,b,c;
int index;
Q(int _a,int _b,int _c,int _index){
a=_a,b=_b,c=_c,index=_index;
}
};
int n,q;
int arr[200005];
int l[200005];
int r[200005];
vector<int> stk;
vector<upd> ru;
vector<upd> du;
vector<Q> queries;
ll ans[200005];
void tri(int i,int j,ll val){
//cout<<i<<" "<<j<<" "<<val<<endl;
if (j<i) return; //stupid shit
diag.update(i,200005,val);
rect.update(j+1,200005,-val);
du.push_back(upd(j-i,i,200005,val));
ru.push_back(upd(j-i,j+1,200005,-val));
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
rep(x,1,n+1) cin>>arr[x];
rep(x,1,n+1){
while (!stk.empty() && arr[stk.back()]<arr[x]){
r[stk.back()]=x-1;
stk.pop_back();
}
stk.push_back(x);
}
while (!stk.empty()){
r[stk.back()]=n;
stk.pop_back();
}
rep(x,n+1,1){
while (!stk.empty() && arr[stk.back()]<=arr[x]){
l[stk.back()]=x+1;
stk.pop_back();
}
stk.push_back(x);
}
while (!stk.empty()){
l[stk.back()]=-200005; //yea
stk.pop_back();
}
rep(x,1,n+1){
tri(l[x],x-1,-arr[x]);
tri(x+1,r[x],-arr[x]);
tri(l[x],r[x],arr[x]);
}
int a,b,c;
rep(x,0,q){
cin>>a>>b>>c;
queries.push_back(Q(a,b,c,x));
}
sort(all(queries),[](Q &i,Q &j){
return i.a<j.a;
});
sort(all(du),[](upd &i,upd &j){
return i.row>j.row;
});
sort(all(ru),[](upd &i,upd &j){
return i.row>j.row;
});
for (auto &it:queries){
while (!du.empty() && du.back().row<it.a){
diag.update(du.back().s,du.back().e,-du.back().val);
du.pop_back();
}
while (!ru.empty() && ru.back().row<it.a){
rect.update(ru.back().s,ru.back().e,-ru.back().val);
ru.pop_back();
}
ans[it.index]=rect.query(it.b,it.c)+diag.query(it.b-it.a,it.c-it.a);
}
rep(x,0,q) cout<<ans[x]<<endl;
}
