# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll mod=998'244'353;
const ll MOD=1e9+7;
struct UF
{
vector<int> par;
void _init(int n)
{
par.resize(n+1);
iota(all(par),0);
}
int _find(int x)
{
if(par[x]==x) return x;
return par[x]=_find(par[x]);
}
void _merge(int x,int y)
{
int fx=_find(x),fy=_find(y);
if(fx==fy) return;
if(fx>fy) swap(fx,fy);
par[fy]=fx;
}
};
struct MaxSeg
{
vector<ll> arr;
vector<ll> seg;
ll seg_init(int v,int l,int r)
{
if(l==r)
{
seg[v]=arr[l];
return seg[v];
}
int mid=(l+r)/2;
return seg[v]=max(seg_init(v*2,l,mid),seg_init(v*2+1,mid+1,r));
}
void _init(int n,vector<ll> t)
{
arr.resize(n+10);
seg.resize(n*4+10);
for(int i=0;i<t.size();i++)
arr[i]=t[i];
seg_init(1,0,n-1);
}
void update(int v,int l,int r,int idx,ll num)
{
if(l>idx || r<idx) return;
if(l==r)
{
seg[v]=num;
return;
}
int mid=(l+r)/2;
update(v*2,l,mid,idx,num);
update(v*2+1,mid+1,r,idx,num);
seg[v]=max(seg[v*2],seg[v*2+1]);
}
ll query(int v,int l,int r,int s,int e)
{
if(l>e || r<s) return -1e18;
if(l>=s && r<=e) return seg[v];
int mid=(l+r)/2;
return max(query(v*2,l,mid,s,e),query(v*2+1,mid+1,r,s,e));
}
};
struct MinSeg
{
vector<ll> arr;
vector<ll> seg;
ll seg_init(int v,int l,int r)
{
if(l==r)
{
seg[v]=arr[l];
return seg[v];
}
int mid=(l+r)/2;
return seg[v]=min(seg_init(v*2,l,mid),seg_init(v*2+1,mid+1,r));
}
void _init(int n,vector<ll> t)
{
arr.resize(n+10);
seg.resize(n*4+10);
for(int i=0;i<t.size();i++)
arr[i]=t[i];
seg_init(1,0,n-1);
}
void update(int v,int l,int r,int idx,ll num)
{
if(l>idx || r<idx) return;
if(l==r)
{
seg[v]=num;
return;
}
int mid=(l+r)/2;
update(v*2,l,mid,idx,num);
update(v*2+1,mid+1,r,idx,num);
seg[v]=min(seg[v*2],seg[v*2+1]);
}
ll query(int v,int l,int r,int s,int e)
{
if(l>e || r<s) return 1e18;
if(l>=s && r<=e) return seg[v];
int mid=(l+r)/2;
return min(query(v*2,l,mid,s,e),query(v*2+1,mid+1,r,s,e));
}
};
struct SumSeg
{
vector<ll> arr;
vector<ll> seg;
ll seg_init(int v,int l,int r)
{
if(l==r)
{
seg[v]=arr[l];
return seg[v];
}
int mid=(l+r)/2;
return seg[v]=seg_init(v*2,l,mid)+seg_init(v*2+1,mid+1,r);
}
void _init(int n,vector<ll> t)
{
arr.resize(n+10);
seg.resize(n*4+10);
for(int i=0;i<t.size();i++)
arr[i]=t[i];
seg_init(1,0,n-1);
}
void update(int v,int l,int r,int idx,ll num)
{
if(l>idx || r<idx) return;
if(l==r)
{
seg[v]=num;
return;
}
int mid=(l+r)/2;
update(v*2,l,mid,idx,num);
update(v*2+1,mid+1,r,idx,num);
seg[v]=seg[v*2]+seg[v*2+1];
}
ll query(int v,int l,int r,int s,int e)
{
if(l>e || r<s) return 0ll;
if(l>=s && r<=e) return seg[v];
int mid=(l+r)/2;
return query(v*2,l,mid,s,e)+query(v*2+1,mid+1,r,s,e);
}
};
SumSeg fire;
int n,q;
ll arr[200010];
pair<int,pair<pll,int>> query[200010];
int p[200010];
ll ans[2000010];
int main()
{
fastio;
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>arr[i];
vector<ll> brr;
for(int i=1;i<=n;i++) brr.push_back(arr[i]);
for(int i=1;i<=q;i++)
{
cin>>query[i].fi>>query[i].se.fi.fi>>query[i].se.fi.se;
query[i].se.se=i;
}
stack<int> s;
for(int i=1;i<=n;i++)
{
while(!s.empty() && arr[s.top()]<=arr[i]) s.pop();
if(!s.empty()) p[i]=s.top();
s.push(i);
}
vector<pair<int,pll>> v;
for(int i=1;i<=n;i++)
{
int cur=p[i];
while(cur)
{
v.push_back({i-cur,{i-1,arr[cur]}});
cur=p[cur];
}
}
sort(all(v));
sort(query+1,query+q+1);
int idx=0;
fire._init(n,brr);
for(int i=1;i<=q;i++)
{
int t=query[i].fi;
int l=query[i].se.fi.fi-1,r=query[i].se.fi.se-1;
while(idx<v.size() && v[idx].fi<=t)
{
//cout<<i<<" | "<<v[idx].fi<<" "<<v[idx].se.fi<<" "<<v[idx].se.se<<'\n';
fire.update(1,0,n-1,v[idx].se.fi,v[idx].se.se);
idx++;
}
ans[query[i].se.se]=fire.query(1,0,n-1,l,r);
}
for(int i=1;i<=q;i++)
cout<<ans[i]<<'\n';
}
