//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 100000000099
ll n,q,t,a,b,c,k,e,m,h,w,u,pier,ost;
ll co[200007],co2[200007],ans[200007];
ll sgtree[POT][2],lazy[POT][2];
stack<pair<ll,ll>>st;//co, idx
vector<ll>v;
vector<pair<pair<ll,ll>,pair<ll,ll>>>zap;
vector<pair<pair<ll,ll>,ll>>p3;
vector<pair<pair<ll,ll>,pair<ll,ll>>>p1,p2;//kiedy,co,gdzie
void spych(ll v,ll l,ll r,ll co){
sgtree[v*2][co]+=(r-l+1)/2*lazy[v][co];
sgtree[v*2+1][co]+=(r-l+1)/2*lazy[v][co];
lazy[v*2][co]+=lazy[v][co];
lazy[v*2+1][co]+=lazy[v][co];
lazy[v][co]=0;
}
void add(ll pocz,ll kon, ll l,ll r,ll val,ll v,ll co){
if(pocz>r || kon<l)return;
if(l>=pocz && kon>=r){
sgtree[v][co]+=(r-l+1)*val;
lazy[v][co]+=val;
}
else{
spych(v,l,r,co);
add(pocz,kon,l,(l+r)/2,val,v*2,co);
add(pocz,kon,(l+r)/2+1,r,val,v*2+1,co);
sgtree[v][co]=sgtree[v*2][co]+sgtree[v*2+1][co];
}
}
ll sm(ll pocz,ll kon,ll l,ll r,ll v,ll co){
if(pocz>r || kon<l)return 0;
if(l>=pocz && kon>=r)return sgtree[v][co];
else{
spych(v,l,r,co);
return sm(pocz,kon,l,(l+r)/2,v*2,co)+sm(pocz,kon,(l+r)/2+1,r,v*2+1,co);}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>q;
for(ll i=0;i<n;i++){
cin>>a;
v.pb(a);
while(st.size() && st.top().ff<=a){
co[st.top().ss]=i;
st.pop();
}
st.push({a,i});
}
while(st.size()){
co[st.top().ss]=n;
st.pop();
}
for(ll i=n-1;i>=0;i--){
a=v[i];
while(st.size() && st.top().ff<=a){
co2[st.top().ss]=i;
st.pop();
}
st.push({a,i});
}
while(st.size()){
co2[st.top().ss]=-200002;
st.pop();
}
for(ll i=0;i<n;i++){
p3.pb({{i-1,i-co2[i]-2},-v[i]});
p3.pb({{co[i]-1,co[i]-i-2},-v[i]});
p3.pb({{co[i]-1,co[i]-co2[i]-2},v[i]});
}
for(auto i : p3){
p1.pb({{0,i.ss},{0,i.ff.ff}});
p1.pb({{i.ff.ss+1,-i.ss},{0,i.ff.ff}});
p2.pb({{0,-i.ss},{0,i.ff.ff-1-i.ff.ss}});
p2.pb({{i.ff.ss+1,i.ss},{0,i.ff.ff-1-i.ff.ss}});
}
sort(p1.begin(),p1.end());
sort(p2.begin(),p2.end());
reverse(p1.begin(),p1.end());
reverse(p2.begin(),p2.end());
for(ll i=0;i<q;i++){
cin>>a>>b>>c;
b--;
c--;
a=min(a,n-1);
zap.pb({{a,i},{b,c}});
}
sort(zap.begin(),zap.end());
for(auto i : zap){
while(p1.size() && i.ff.ff>=p1.back().ff.ff){
add(1+p1.back().ss.ff,1+p1.back().ss.ss,1,POT/2,p1.back().ff.ss,1,0);
p1.pop_back();
}
while(p2.size() && i.ff.ff>=p2.back().ff.ff){
add(1,300007+p2.back().ss.ss,1,POT/2,p2.back().ff.ss,1,1);
p2.pop_back();
}
ans[i.ff.ss]=sm(1+i.ss.ff,1+i.ss.ss,1,POT/2,1,0)+sm(300007-i.ff.ff+i.ss.ff,300007-i.ff.ff+i.ss.ss,1,POT/2,1,1);
}
for(ll i=0;i<q;i++)cout<<ans[i]<<"\n";
}
