#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
int S[200000];
LLI pre[200001],pre2[200001];
struct query { int T,L,R,i; };
bool comp(query a,query b) {
return a.T < b.T;
}
query queries[200000];
LLI ans[200000];
int l[200000],depth[200000];
vi SS;
vpii events[200005];
LLI bit[200001];
int main() {
int i;
int N,Q,T,L,R;
scanf("%d %d",&N,&Q);
for (i = 0; i < N; i++) scanf("%d",&S[i]);
for (i = 0; i < Q; i++) {
scanf("%d %d %d",&T,&L,&R);
queries[i] = (query){T+1,L-1,R-1,i};
}
sort(queries,queries+Q,comp);
LLI sum = 0;
for (i = 0; i < N; i++) {
while (!SS.empty() && (S[SS.back()] <= S[i])) SS.pop_back();
if (SS.empty()) l[i] = -1,depth[i] = 0;
else l[i] = SS.back(),depth[i] = depth[l[i]]+1;
SS.pb(i),sum += depth[i];
}
if (1) {
for (i = 0; i < N; i++) {
int u = i,p = 0;
while (u != -1) {
events[i-u+1].pb(mp(i,S[u]-p));
p = S[u],u = l[u];
}
}
int j = 0,k,l;
for (i = 0; i < Q; i++) {
while (j <= queries[i].T) {
for (k = 0; k < events[j].size(); k++) {
for (l = events[j][k].first+1; l <= N; l += l & (-l)) bit[l] += events[j][k].second;
}
j++;
}
LLI a = 0;
for (l = queries[i].R+1; l > 0; l -= l & (-l)) a += bit[l];
for (l = queries[i].L; l > 0; l -= l & (-l)) a -= bit[l];
ans[queries[i].i] = a;
}
for (i = 0; i < Q; i++) printf("%lld\n",ans[i]);
return 0;
}
int j,c = 1;
int k = 0,f = 0;
for (i = 0; i < Q; i++) {
if ((i > 0) && (queries[i].T != queries[i-1].T)) f = 0;
while (queries[i].T >= 2*c) {
for (j = N-1; j >= c; j--) S[j] = max(S[j],S[j-c]);
for (j = 0; j < N; j++) pre[j+1] = pre[j]+S[j];
c *= 2;
}
int d = queries[i].T-c;
while ((k < Q) && (queries[k].T == queries[i].T)) k++;
if (!f && (k-i > 10)) {
f = 1;
for (j = 0; j < N; j++) pre2[j+1] = pre2[j]+max(S[j],(j >= d) ? S[j-d]:0);
}
if (f) ans[queries[i].i] = pre2[queries[i].R+1]-pre2[queries[i].L];
else {
LLI a = 0;
if (d > queries[i].L) a += pre[min(d,queries[i].R+1)]-pre[queries[i].L];
int e = max(d,queries[i].L);
if (e <= queries[i].R) {
int *p = S+e,*q = S+(e-d);
int t = queries[i].R-e+1;
int tt = (t/4)*4;
for (j = 0; j < tt; j += 4) {
a += (p[j] > q[j]) ? p[j]:q[j];
a += (p[j+1] > q[j+1]) ? p[j+1]:q[j+1];
a += (p[j+2] > q[j+2]) ? p[j+2]:q[j+2];
a += (p[j+3] > q[j+3]) ? p[j+3]:q[j+3];
}
for (; j < t; j++) a += (p[j] > q[j]) ? p[j]:q[j];
}
ans[queries[i].i] = a;
}
}
for (i = 0; i < Q; i++) printf("%lld\n",ans[i]);
return 0;
}
