#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int MAX=1e6+5;
int N,M;
int A[MAX];
vector<pii> E[MAX]; // {s,qi}
int T[MAX];
int ans[MAX];
struct SRQ{
int s,e,m,d;
SRQ *l,*r;
vector<int> vctl,vctr;
SRQ(int s,int e):s(s),e(e),m((s+e)/2),d(e-s+1){
vctl.resize(d),vctr.resize(d);
vector<int> mval(m+1-s); // Max
int p=0;
for (int x=m;x>=s;x--) p=max(p,A[x]),mval[m-x]=p;
set<int> se;
for (int y=m+1;y<=e;y++){
se.insert(A[y]);
for (auto [si,qi]:E[y]){
if (si<s||si>m) continue;
auto it=se.lower_bound(mval[m-si]);
if (it==se.begin()) continue;
it--;
ans[qi]=max(ans[qi],mval[m-si]+*it);
}
auto it=se.lower_bound(p);
if (it==se.begin()) vctl[y-s]=0;
else vctl[y-s]=p+*prev(it);
}
for (int x=m;x>=s;x--){
auto it=se.lower_bound(mval[m-x]);
if (it==se.begin()) vctr[x-s]=0;
else vctr[x-s]=mval[m-x]+*prev(it);
}
if (d==1) return;
l=new SRQ(s,m);
r=new SRQ(m+1,e);
for (int x=s;x<=m;x++){
vctl[x-s]=max(vctl[x-s],l->vctl[x-l->s]);
vctr[x-s]=max(vctr[x-s],l->vctr[x-l->s]);
vctr[x-s]=max(vctr[x-s],r->vctr.front());
}
for (int x=m+1;x<=e;x++){
vctr[x-s]=max(vctr[x-s],r->vctr[x-r->s]);
vctl[x-s]=max(vctl[x-s],r->vctl[x-r->s]);
vctl[x-s]=max(vctl[x-s],l->vctl.back());
}
}
int qry(int x,int y){
if (d==1) return 0;
if (y<=m) return l->qry(x,y);
if (x>m) return r->qry(x,y);
return max(l->vctr[x-l->s],r->vctl[y-r->s]);
}
};
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>N>>M;
for (int i=0;i<N;i++) cin>>A[i];
for (int qi=0;qi<M;qi++){
int s,e,k;cin>>s>>e>>k;s--,e--;
E[e].push_back({s,qi});
T[qi]=k;
}
auto srq=new SRQ(0,N-1);
for (int e=0;e<N;e++) for (auto [s,qi]:E[e]){
ans[qi]=max(ans[qi],srq->qry(s,e));
}
for (int i=0;i<M;i++) cout<<ans[i]<<'\n';
//for (int i=0;i<M;i++) cout<<(ans[i]<=T[i])<<'\n';
}
