#include<bits/stdc++.h>
using namespace std;
const long long maxn=400000+10;
struct fenwick{
long long fn[maxn];
void clear(){
for(long long i=0;i<maxn;i++){
fn[i]=0;
}
}
void upd(long long l,long long r,long long w){
//cout<<"upd: "<<l<<" "<<r<<" "<<w<<endl;
l++;
r++;
if(l>r){
return ;
}
r++;
while(l<maxn){
fn[l]+=w;
l+=((-l)&l);
}
while(r<maxn){
fn[r]-=w;
r+=((-r)&r);
}
}
long long pors(long long i){
long long ret=0;
i++;
while(i>0){
ret+=fn[i];
i-=((-i)&i);
}
return ret;
}
}sumw,sumwe;
struct que{
long long ind,l,r;
}allq[maxn];
struct ezaf{
long long sot,pa,tp,w;
long long qq,radif,soton,z;
ezaf(){
qq=-1;
}
};
long long n,q;
long long all[maxn],dpl[maxn],dpr[maxn],res[maxn];
vector<ezaf>amood,mov;
void vorod(){
cin>>n>>q;
for(long long i=1;i<=n;i++){
cin>>all[i];
}
for(long long i=1;i<=q;i++){
cin>>allq[i].ind>>allq[i].l>>allq[i].r;
}
}
void caldp(){
vector<long long>v;
for(long long i=1;i<=n;i++){
while((long long)v.size()>0&&all[v.back()]<=(long long)all[i]){
v.pop_back();
}
if((long long)v.size()==0){
dpl[i]=-1;
}else{
dpl[i]=v.back();
}
v.push_back(i);
}
v.clear();
for(long long i=n;i>=1;i--){
while((long long)v.size()>0&&all[v.back()]<(long long)all[i]){
v.pop_back();
}
if((long long)v.size()==0){
dpr[i]=-1;
}else{
dpr[i]=v.back();
}
v.push_back(i);
}
}
void pre(){
caldp();
for(long long i=1;i<=q;i++){
ezaf e;
e.qq=i;
e.radif=allq[i].ind;
e.soton=allq[i].l-1;
e.z=-1;
amood.push_back(e);
mov.push_back(e);
e.soton=allq[i].r;
e.z=1;
amood.push_back(e);
mov.push_back(e);
}
for(long long i=1;i<=n;i++){
long long lenamood,lenmov;
if(dpl[i]==-1){
lenamood=n+5;
}else{
lenamood=i-dpl[i];
}
if(dpr[i]==-1){
lenmov=n+5;
}else{
lenmov=dpr[i]-i;
}
////cout<<"chy: "<<i<<" "<<lenamood<<" "<<lenmov<<endl;
ezaf e;
e.sot=i;
e.pa=0;
e.tp=lenamood-2;
e.w=all[i];
amood.push_back(e);
e.pa=lenamood-1;
e.tp=lenamood-1+lenmov-1;
mov.push_back(e);
e.sot=i+1;
e.pa=0;
e.tp=lenmov-2;
e.w=-all[i];
mov.push_back(e);
e.sot=i+1+lenmov-2+1;
e.pa=lenmov-2+1;
e.tp=e.pa+lenamood-1;
amood.push_back(e);
}
}
bool cmpamood(ezaf a,ezaf b){
long long la,lb;
if(a.qq==-1){
la=a.sot;
}else{
la=a.soton;
}
if(b.qq==-1){
lb=b.sot;
}else{
lb=b.soton;
}
if(la==lb){
return a.qq<b.qq;
}
return la<lb;
}
bool cmpmov(ezaf a,ezaf b){
long long la,lb;
if(a.qq==-1){
la=a.sot-a.pa;
}else{
la=a.soton-a.radif;
}
if(b.qq==-1){
lb=b.sot-b.pa;
}else{
lb=b.soton-b.radif;
}
if(la==lb){
return a.qq<b.qq;
}
return la<lb;
}
void solve(){
sort(amood.begin(),amood.end(),cmpamood);
sort(mov.begin(),mov.end(),cmpmov);
for(auto x:amood){
if(x.qq==-1){
// //cout<<"wtf: "<<x.w<<endl;
sumw.upd(x.pa,x.tp,x.w);
sumwe.upd(x.pa,x.tp,-x.w*(x.sot-1));
}else{
//cout<<"pors: "<<x.qq<<" "<<x.radif<<" "<<x.soton<<endl;
long long fake=sumw.pors(x.radif)*x.soton+sumwe.pors(x.radif);
res[x.qq]+=fake*x.z;
}
}
sumw.clear();
sumwe.clear();
for(auto x:mov){
if(x.qq==-1){
////cout<<"wtf: "<<x.sot<<" "<<x.pa<<" "<<x.tp<<endl;
//cout<<x.sot<<" hey:"<<endl;
sumw.upd(x.pa,x.tp,x.w);
sumwe.upd(x.pa,x.tp,-x.w*(x.sot-x.pa-1));
}else{
//cout<<"pors: "<<x.qq<<" "<<x.radif<<" "<<x.soton<<endl;
long long fake=sumw.pors(x.radif)*(x.soton-x.radif)+sumwe.pors(x.radif);
res[x.qq]+=fake*x.z;
}
}
}
void khor(){
for(long long i=1;i<=q;i++){
cout<<res[i]<<"\n";
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
//cout.tie(0);
//freopen("inp.txt","r",stdin);
vorod();
pre();
solve();
khor();
}
