#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 node{
int s,e,m;
ll val=0,lazy=0;
node *l=nullptr,*r=nullptr;
node(int _s,int _e){
s=_s,e=_e,m=s+e>>1;
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
ll propo(){
if (lazy){
val+=lazy*(e-s+1);
if (s!=e) l->lazy+=lazy,r->lazy+=lazy;
lazy=0;
}
return val;
}
void update(int i,int j,ll k){
if (s==i && e==j) lazy+=k;
else{
if (j<=m) l->update(i,j,k);
else if (m<i) r->update(i,j,k);
else l->update(i,m,k),r->update(m+1,j,k);
val=l->propo()+r->propo();
}
}
ll query(int i,int j){
propo();
if (s==i && e==j) return val;
else if (j<=m) return l->query(i,j);
else if (m<i) return r->query(i,j);
else return l->query(i,m)+r->query(m+1,j);
}
}*rect=new node(-200005,200005),*diag=new node(-200005,200005);
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;
}
