#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Fenwick {
int n;
vector<ll> f;
Fenwick(int _n): n(_n), f(n+1,0) {}
void update(int i, ll v) {
for (; i<=n; i+=i&-i) f[i]+=v;
}
ll query(int i) {
ll s=0;
for (; i>0; i-=i&-i) s+=f[i];
return s;
}
ll rangeQuery(int l, int r) {
return query(r) - query(l-1);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int N, Q;
cin >> N >> Q;
vector<ll> A(N+1);
for(int i=1;i<=N;i++) cin>>A[i];
// 1) 이전 더 큰 원소
vector<int> p(N+1);
stack<int> st;
for(int i=1;i<=N;i++){
while(!st.empty() && A[st.top()]<=A[i]) st.pop();
p[i] = st.empty() ? 0 : st.top();
st.push(i);
}
// 2) 이벤트 생성
struct Event{int t, pos; ll delta;};
vector<Event> events;
events.reserve(N);
for(int i=1;i<=N;i++){
ll last = A[i];
int j = p[i];
while(j>0){
events.push_back({i-j, i, A[j]-last});
last = A[j];
j = p[j];
}
}
sort(events.begin(), events.end(), [](auto &a, auto &b){return a.t < b.t;});
// 3) 쿼리 입력 및 정렬
struct Query{int T,L,R,idx;};
vector<Query> qs(Q);
for(int i=0;i<Q;i++){
cin>>qs[i].T>>qs[i].L>>qs[i].R;
qs[i].idx = i;
}
sort(qs.begin(), qs.end(), [](auto &a, auto &b){return a.T < b.T;});
// 4) Fenwick 초기화
Fenwick fw(N);
for(int i=1;i<=N;i++) fw.update(i, A[i]);
vector<ll> ans(Q);
int ei = 0;
// 5) 시간 순 처리
for(auto &q: qs){
while(ei < events.size() && events[ei].t <= q.T){
fw.update(events[ei].pos, events[ei].delta);
ei++;
}
ans[q.idx] = fw.rangeQuery(q.L, q.R);
}
// 6) 결과 출력
for(ll x: ans) cout<<x<<"\n";
return 0;
}
