#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=2e5+50;
const int mod=1e9+7;
using namespace std;
int n,q,i,lf[nmax],rg[nmax],x,r[nmax],j,v[nmax];
ll a[nmax],b[nmax],fw[nmax],rs[nmax];
vector<int>vc[nmax],ad,dl[nmax],nw;
stack<int>st;
void upd(int i,ll vl)
{
for(;i<=n;i+=i&(-i))fw[i]+=vl;
}
ll qry(int i)
{
ll rs=0;
for(;i>=1;i-=i&(-i))rs+=fw[i];
return rs;
}
ll qry(int l,int r)
{
ll rs=qry(r);
if(l>1)rs-=qry(l-1);
return rs;
}
int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
cin>>n>>q;
for(i=1;i<=n;i++)cin>>a[i];
for(i=1;i<=q;i++)
{
cin>>x>>lf[i]>>rg[i];
vc[x].pb(i);
}
/*for(i=1;i<=n;i++)
{
while(!st.empty() && a[st.top()]<=a[i])st.pop();
if(st.empty())l[i]=1;
else l[i]=st.top()+1;
st.push(i);
}
while(!st.empty())st.pop();*/
for(i=n;i>=1;i--)
{
while(!st.empty() && a[st.top()]<=a[i])st.pop();
if(st.empty())r[i]=n;
else r[i]=st.top()-1;
st.push(i);
}
for(i=1;i<=n;i++)
{
b[i]=a[i];
upd(i,a[i]);
ad.pb(i);
v[i]=1;
dl[r[i]-i+1].pb(i);
}
for(i=1;i<=n;i++)
{
for(j=0;j<(int)dl[i].size();j++)v[dl[i][j]]=0;
nw.clear();
for(j=0;j<(int)ad.size();j++)if(v[ad[j]])nw.pb(ad[j]);
ad=nw;
for(j=0;j<(int)ad.size();j++)
{
upd(ad[j]+i,-b[ad[j]+i]);
b[ad[j]+i]=a[ad[j]];
upd(ad[j]+i,b[ad[j]+i]);
}
for(j=0;j<(int)vc[i].size();j++)
{
rs[vc[i][j]]=qry(lf[vc[i][j]],rg[vc[i][j]]);
}
}
for(i=1;i<=q;i++)cout<<rs[i]<<'\n';
return 0;
}
