#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;
void solve1(){
Seg.Init(N);
for(int i=0; i<vt.size(); i++){
ST now = vt[i];
ll answer = 0;
for(int j=now.l; j<=now.r; j++){
answer += (ll)Seg.Mx(j-now.t, j);
}
printf("%lld\n", answer);
}
}
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;
}
void solve2(){
Seg.Init(N);
int T = vt[0].t;
for(int i=1; i<=N; i++){
upd(i, (ll)Seg.Mx(i-T, i));
}
for(int i=0; i<vt.size(); i++){
ST now = vt[i];
printf("%lld\n", Sum(now.r) - Sum(now.l-1));
}
}
void solve3(){
Seg.Init(N);
for(int i=0; i<vt.size(); i++){
ST now = vt[i];
printf("%lld\n", (ll)Seg.Mx(now.l-now.t, now.l));
}
}
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]);
}
bool tf2 = true, tf3 = true;
for(int i=1; i<=Q; i++){
int t, l, r; scanf("%d%d%d", &t, &l, &r);
vt.pb({t, l, r, i});
if(t!=vt[0].t) tf2 = false;
if(l!=r) tf3 = false;
}
if(N<=200 && Q<=200){
solve1();
}else if(tf2){
solve2();
}else if(tf3){
solve3();
}else{
solve4();
}
return 0;
}
