#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;
ll a[nmax],b[nmax],fw[nmax],rs[nmax];
vector<int>vc[nmax];
stack<int>st;
set<int>ad,dl[nmax];
set<int>::iterator it;
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.in(i);
dl[r[i]-i+1].in(i);
}
for(i=1;i<=n;i++)
{
for(it=dl[i].begin();it!=dl[i].end();it++)ad.er(ad.fd(*it));
for(it=ad.begin();it!=ad.end();it++)
{
upd((*it)+i,-b[(*it)+i]);
b[(*it)+i]=a[*it];
upd((*it)+i,b[(*it)+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;
}
