#include<bits/stdc++.h>
#pragma GCC optimize("trapv")
#define st first
#define nd second
using namespace std;
using ll = long long;
const int N=1<<18;
int tab[N], L[N], R[N];
int ile[N+N];
ll sum[N+N];
set<int> S;
int n;
int pra(int i){
//cout<<i<<" "<<ile[n+N+1]<<endl;
//assert(ile[N+n+1]);
for(i+=N; i>0; i/=2){
if((i&1)==0 && ile[i+1]){
i++;
while(i<N){
if(ile[i+i])i=i+i;
else i=i+i+1;
}
//cout<<"? "<<i-N<<endl;
return i-N;
}
}
assert(false);
return 0;
}
int lew(int i){
for(i+=N; i>0; i/=2){
if((i&1) && ile[i-1]){
i--;
while(i<N){
if(ile[i+i+1])i=i+i+1;
else i=i+i;
}
//cout<<"? "<<i-N<<endl;
return i-N;
}
}
assert(false);
return 0;
}
void upd(int i){
if(i==0 || i==n+1)return;
//cout<<i<<"u"<<endl;
if(S.find(i)!=S.end())S.erase(S.find(i));
//cout<<i<<"a"<<lew(i)<<" "<<tab[lew(i)]<<" "<<tab[i]<<"\n";
L[i]=(tab[lew(i)]>tab[i]);
R[i]=(tab[pra(i)]<tab[i]);
if(L[i]^R[i]){
S.insert(i);
}
//cout<<i<<"u"<<endl;
}
void usun(int i){
//cout<<"- "<<i<<endl;
int ii=i;
for(i+=N; i>0; i>>=1){
sum[i]-=tab[ii];
ile[i]--;
assert(ile[i]>=0);
}
upd(lew(ii));
upd(pra(ii));
if(ile[ii+N]==0)S.erase(S.find(ii));
}
void dodaj(int i){
int ii=i;
for(i+=N; i>0; i>>=1){
sum[i]+=tab[ii];
ile[i]++;
}
}
ll quer(int k){
ll ans=0;
int v=1;
while(v<N){
if(ile[v+v]<=k){
k-=ile[v+v];
ans+=sum[v+v];
v=v+v+1;
}
else v=v+v;
}
assert(k<=ile[v]);
if(k)ans+=k*1ll*tab[v-N];
return ans;
}
int main(){
int q;
cin>>n>>q;
tab[0]=0;
ile[N]=1;
for(int i=1; i<=n; i++){
cin>>tab[i];
ile[N+i]=1;
sum[N+i]=tab[i];
}
tab[n+1]=1e9+5;
ile[n+1+N]=1;
for(int i=N-1; i>0; i--){
ile[i]=ile[i+i]+ile[i+i+1];
sum[i]=sum[i+i]+sum[i+i+1];
}
for(int i=1; i<=n; i++){
upd(i);
//cout<<L[i]<<" "<<R[i]<<"\n";
}
vector<pair<pair<int, int>, pair<int, int> > > Q(q);
for(int i=0; i<q; i++){
Q[i].st.nd=i;
cin>>Q[i].st.st>>Q[i].nd.st>>Q[i].nd.nd;
Q[i].nd.nd++;
}
vector<ll> ans(q);
sort(Q.begin(), Q.end());
int wsk=0;
//assert(S.find(0)==S.end());
for(int t=1; t<=n; t++){
//cout<<t<<"aaa"<<endl;
vector<int> V, V2;
for(auto it=S.begin(); it!=S.end(); it++){
//cout<<*it<<"\n";
//V.push_back(*it);
if(L[*it])V.push_back(*it);
else V2.push_back(*it);
}
/*for(int i:V)
{
//assert(i!=0);
if(L[i]){
//cout<<"- "<<i<<endl;
usun(i);
}
else{
//cout<<"+ "<<i<<endl;
dodaj(i);
}
}*/
for(int i:V2)dodaj(i);
for(int i:V)usun(i);
//return 0;
/*if(t==1){
cout<<quer(1)<<" "<<quer(2)<<" "<<quer(3)<<" "<<quer(4)<<"\n";
}*/
while(wsk<q && Q[wsk].st.st==t){
ans[Q[wsk].st.nd]=quer(Q[wsk].nd.nd)-quer(Q[wsk].nd.st);
wsk++;
}
}
for(int i=0; i<q; i++)cout<<ans[i]<<"\n";
}
