#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
const int MAX_N = 200000;
int N, Q;
int S[MAX_N+1];
struct ST{
int t, l, r, idx;
bool operator <(const ST &a)const{
return t<a.t;
}
};
vector<ST> vt;
struct SEG{
struct NODE{
int l, r;
int mx;
};
vector<NODE> seg;
int SZ;
void add(){
seg.pb({-1, -1, 0});
}
void Init(int x){
SZ = x;
add(); init(0, 1, SZ);
}
void init(int idx, int s, int e){
if(s==e) {
seg[idx].mx = S[s];
return;
}
seg[idx].l = seg.size(); add();
seg[idx].r = seg.size(); add();
init(seg[idx].l, s, (s+e)/2);
init(seg[idx].r, (s+e)/2+1, e);
seg[idx].mx = max(seg[seg[idx].l].mx, seg[seg[idx].r].mx);
}
int Mx(int x, int y){
return mx(0, 1, SZ, x, y);
}
int mx(int idx, int s, int e, int x, int y){
if(x>e || y<s) return 0;
if(x<=s && e<=y) return seg[idx].mx;
return max(mx(seg[idx].l, s, (s+e)/2, x, y), mx(seg[idx].r, (s+e)/2+1, e, x, y));
}
}Seg;
ll tree[MAX_N+1];
void upd(int x, ll y){
while(x<=N){
tree[x]+=y;
x+=(x&-x);
}
}
ll Sum(int x){
ll ret = 0;
while(x>0){
ret+=tree[x];
x-=(x&-x);
}
return ret;
}
ll ans[MAX_N+1];
vector<pii> v, v2;
void solve4(){
Seg.Init(N);
sort(vt.begin(), vt.end());
int T = 0;
for(int i=1; i<=N; i++){
upd(i, S[i]);
if(S[i]!=0){
v.pb({i, S[i]});
}
}
for(int i=0; i<vt.size(); i++){
ST now = vt[i];
while(T<now.t){
T++;
while(!v.empty()){
pii n = v.back(); v.pop_back();
if(n.first==N) continue;
if(S[n.first+1]<n.second){
upd(n.first+1, (ll)(n.second-S[n.first+1]));
S[n.first+1] = n.second;
v2.pb({n.first+1, n.second});
}
}
while(!v2.empty()){
v.pb(v2.back()); v2.pop_back();
}
}
ans[now.idx] = Sum(now.r) - Sum(now.l-1);
}
for(int i=1; i<=Q; i++){
printf("%lld\n", ans[i]);
}
}
int main(){
scanf("%d%d", &N, &Q);
for(int i=1; i<=N; i++){
scanf("%d", &S[i]);
}
for(int i=1; i<=Q; i++){
int t, l, r; scanf("%d%d%d", &t, &l, &r);
vt.pb({t, l, r, i});
}
solve4();
return 0;
}
