#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
struct line{
ll a,b;
ll get_val(ll x){
return a*x+b;
}
};
line operator+(const line &l1,const line &l2){
return {l1.a+l2.a,l1.b+l2.b};
}
line operator*(const line &l,const ll k){
return {l.a*k,l.b*k};
}
struct us{
int t,x;
line l;
bool operator<(const us &tmp){
if (t!=tmp.t)
return t<tmp.t;
return l.a>tmp.l.a;
}
};
struct qs{
int t,l,r,x;
bool operator<(const qs &tmp){
return t<tmp.t;
}
};
struct node{
line sum,cnt;
};
node operator+(const node &a,const node &b){
return {a.sum+b.sum,a.cnt+b.cnt};
}
const ll MAX=1e9+1;
int N,Q;
ll A[200002];
int D1[200001],D2[200001];
node Tree[1<<19];
node update(int x,line v,int l,int r,int n){
if (x<l||r<x)
return Tree[n];
if (l==r)
return Tree[n]={v*A[x],v};
int m=(l+r)>>1;
return Tree[n]=update(x,v,l,m,n<<1)+update(x,v,m+1,r,n<<1|1);
}
ll query(int x,int t,int l,int r,int n){
if (l==r)
return A[l]*x;
int m=(l+r)>>1;
if (x>Tree[n<<1].cnt.get_val(t))
return Tree[n<<1].sum.get_val(t)+query(x-Tree[n<<1].cnt.get_val(t),t,m+1,r,n<<1|1);
return query(x,t,l,m,n<<1);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>N>>Q;
for (int i=1; i<=N; i++)
cin>>A[i];
A[N+1]=MAX;
stack<int> s;
for (int i=1; i<=N; i++){
while (!s.empty()&&A[s.top()]<A[i])
s.pop();
if (!s.empty())
D1[i]=s.top();
s.push(i);
}
while (!s.empty())
s.pop();
s.push(N+1);
for (int i=N; i; i--){
while (A[s.top()]<=A[i])
s.pop();
D2[i]=s.top();
s.push(i);
}
vector<us> vu;
for (int i=1; i<=N; i++){
if (D1[i]){
int t1=i-D1[i]-1,t2=D2[i]-i-1;
if (t1>t2)
swap(t1,t2);
vu.push_back({0,i,{1,1}});
vu.push_back({t1,i,{0,t1+1}});
vu.push_back({t2,i,{-1,t1+t2+1}});
vu.push_back({t1+t2+1,i,{0,0}});
}
else{
int t=D2[i]-i-1;
vu.push_back({0,i,{1,1}});
vu.push_back({t,i,{0,t+1}});
}
}
sort(all(vu));
vector<qs> vq;
for (int i=0,t,l,r; i<Q; i++){
cin>>t>>l>>r;
vq.push_back({t,l,r,i});
}
sort(all(vq));
vector<ll> ans(Q);
for (int t=0,iu=0,iq=0; t<=N; t++){
for (; iu<(int)vu.size()&&vu[iu].t==t; iu++)
update(vu[iu].x,vu[iu].l,1,N,1);
for (; iq<(int)vq.size()&&vq[iq].t==t; iq++)
ans[vq[iq].x]=query(vq[iq].r,t,1,N,1)-query(vq[iq].l-1,t,1,N,1);
}
for (int i=0; i<Q; i++)
cout<<ans[i]<<"\n";
return 0;
}
