#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];
set<int> se;
int mval[MAX]; // Max
int vctl[MAX],vctr[MAX];
struct SRQ{
int s,e,m,d;
SRQ *l,*r;
vector<int> srt;
SRQ(int s,int e):s(s),e(e),m((s+e)/2),d(e-s+1){
srt.resize(d);
if (d>1){
l=new SRQ(s,m);
r=new SRQ(m+1,e);
for (int ei=m+1;ei<=e;ei++){
for (auto [si,qi]:E[ei]){
if (si<s||si>m) continue;
ans[qi]=max(ans[qi],max(vctr[si],vctl[ei]));
}
}
for (int x=s;x<=m;x++) vctr[x]=max(vctr[x],vctr[r->s]);
for (int x=m+1;x<=e;x++) vctl[x]=max(vctl[x],vctl[l->e]);
merge(l->srt.begin(),l->srt.end(),r->srt.begin(),r->srt.end(),srt.begin());
}else{
srt[0]=A[s];
}
int p=0;
for (int x=m;x>=s;x--) p=max(p,A[x]),mval[x]=p;
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[si]);
if (it==se.begin()) continue;
it--;
ans[qi]=max(ans[qi],mval[si]+*it);
}
}
se.clear();
int q=-1;
for (int y=m+1;y<=e;y++){
if (A[y]<p) q=max(q,A[y]);
if (q!=-1) vctl[y]=max(vctl[y],p+q);
}
if (d>1){
int k=r->d-1;
for (int x=s;x<=m;x++){
while (k>=0&&r->srt[k]>=mval[x]) k--;
if (k>=0) vctr[x]=max(vctr[x],mval[x]+r->srt[k]);
}
}
/*
cout<<s<<' '<<m<<' '<<e<<'\n';
for (auto a:vctl) cout<<a<<' ';
cout<<'\n';
for (auto a:vctr) cout<<a<<' ';
cout<<'\n';
cout<<'\n';*/
}
};
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 i=0;i<M;i++) cout<<ans[i]<<'\n';
//for (int i=0;i<M;i++) cout<<(ans[i]<=T[i])<<'\n';
}
