#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
struct qq{
int index,t,l,r;
};
inline int combine(int a, int b){
return a+b;
}
struct node{
int s,e,m;
node *l,*r;
int v;
int lazyUpd;
node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(0),lazyUpd(0){
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void self_add(int x){
v+=(e-s+1)*x;
lazyUpd+=x;
}
void forceProp(){
if(s==e) return;
if(lazyUpd){
l->self_add(lazyUpd); r->self_add(lazyUpd);
lazyUpd=0;
}
}
void rangeUpd(int x, int y, int c){
if(x<=s&&y>=e){
self_add(c);
return;
}
forceProp();
if(x<=m) l->rangeUpd(x,y,c);
if(y>m) r->rangeUpd(x,y,c);
v=combine(l->v,r->v);
}
int query(int x, int y){
if(x<=s&&y>=e){
return v;
}
forceProp();
if(y<=m) return l->query(x,y);
if(x>m) return r->query(x,y);
return combine(l->query(x,m),r->query(m+1,y));
}
};
vector<array<int,3>>storage2[200005]; //normal
vector<array<int,3>>storage3[200005]; //triangle
void f(int index, int a, int sgn, int ptr){
a=min(a,index-1);
if(a<0) return;
//normal
int hold=index-a;
storage2[hold].push_back({a,sgn,ptr});
//triangle
storage3[hold].push_back({a+hold,sgn*-1,ptr});
storage3[index].push_back({hold+a,sgn,ptr});
}
void solve(){
int n,q;
cin >> n >> q;
int arr[n+5];
for(int x=1;x<=n;x++){
cin >> arr[x];
}
qq que[q];
for(int x=0;x<q;x++){
cin >> que[x].t >> que[x].l >> que[x].r;
que[x].index=x;
f(que[x].r,que[x].t,1,x);
f(que[x].l-1,que[x].t,-1,x);
}
vector<int>d;
vector<pair<pii,int>>storage[n+5]; //add
d.push_back(n+1);
for(int x=n;x>=1;x--){
storage[x].push_back({{0,0},arr[x]});
int cur=0;
while(d.size()>1&&arr[d.back()]<arr[x]){
int hold=d.back();
d.pop_back();
int diff=d.back()-hold;
storage[x].push_back({{cur+1,cur+diff},arr[x]-arr[hold]});
cur+=diff;
}
d.push_back(x);
}
node st(0,n+5); //normal
node st2(0,2*n+5); //triangular
int ans[q];
memset(ans,0,sizeof(ans));
for(int x=0;x<=n;x++){
for(auto it:storage[x]){
st.rangeUpd(it.first.first,it.first.second,it.second);
st2.rangeUpd(it.first.first+x,it.first.second+x,it.second);
}
for(auto it:storage2[x]){
ans[it[2]]+=st.query(0,it[0])*it[1];
}
for(auto it:storage3[x]){
ans[it[2]]+=st2.query(0,it[0])*it[1];
}
}
for(int x=0;x<q;x++){
cout << ans[x] << "\n";
}
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("in.txt","r",stdin);
//freopen("in.txt","w",stdout);
int t=1;
//cin >> t;
while(t--){
solve();
}
}
