#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e5 + 12, MOD = (int)1e9 + 7;
int n,q,s[N];
vector<array<int,3>> qr[N];
struct segtree {
vector<ll> t,add;
void init() {
t.assign(N * 4,0);
add.assign(N * 4,0);
}
void inc(int v,ll val,int tl,int tr) {
add[v] += val;
t[v] += val*1ll* (tr - tl + 1);
}
void push(int v,int tl,int tr) {
if(add[v]) {
int tm = (tl + tr) >> 1;
inc(v + v,add[v],tl,tm);
inc(v + v + 1,add[v],tm+1,tr);
add[v] = 0;
}
}
void upd(int l,int r,ll val,int v = 1,int tl = 1,int tr = n) {
if(l > r || tl > r || l > tr) return ;
if(tl >= l && tr <= r) {
inc(v,val,tl,tr);
} else {
push(v,tl,tr);
int tm = (tl + tr) >> 1;
upd(l,r,val,v+v,tl,tm);
upd(l,r,val,v+v+1,tm+1,tr);
t[v] = t[v + v] + t[v + v + 1];
}
}
ll get(int l,int r,int v = 1,int tl = 1,int tr = n) {
if(l > r || tl >r || l > tr) return 0;
if(tl >= l && tr <= r) return t[v];
push(v,tl,tr);
int tm = (tl + tr) >> 1;
return get(l,r,v+v,tl,tm) + get(l,r,v+v+1,tm+1,tr);
}
}t_[3];
int prv[N],nx[N];
vector<array<int,4>> sub[N];
void prec() {
for(int i = 0;i < 3;++i) t_[i].init();
vector<int> st;
for(int i = 1;i <= n;i++) {
while(!st.empty() && s[st.back()] <= s[i]) {
st.pop_back();
}
if(!st.empty()) {
prv[i] = st.back();
}
st.push_back(i);
}
st.clear();
for(int i = n;i >= 1;i--) {
while(!st.empty() && s[st.back()] < s[i]) {
st.pop_back();
}
if(!st.empty()) {
nx[i] = st.back();
} else {
nx[i] = n + 1;
}
st.push_back(i);
}
auto triag = [&](int i,int s,int val) {
++s;
int l = i,r = i + s - 1;
if(l > r) return;
sub[s].push_back({l,n,-val,0});
sub[s].push_back({r+1,n,val,1});
t_[0].upd(l,n,val);
t_[1].upd(r + 1,n,-val);
};
for(int i = 1;i <= n;i++) {
if(prv[i]) {
triag(prv[i] + 1,nx[i] - 1 - (prv[i] + 1),s[i]);
triag(prv[i] + 1,i - prv[i] - 2,-s[i]);
triag(i + 1,(nx[i] - 1) - (i + 1),-s[i]);
} else {
int _s = nx[i] - i;
// cout << i << ' ' << i + _s - 1 << '\n';
t_[1].upd(i,i + _s - 1,s[i]);
// cout << i + 1 << ' ' << _s - 1 << "\n";
triag(i+1,_s-2,-s[i]);
}
}
}
ll ans[N];
void test() {
cin >> n >> q;
for(int i = 1;i <= n;i++) {
cin >> s[i];
}
prec();
for(int i = 1;i <= q;i++) {
int l,r,t;
cin >> t >> l >> r;
qr[t].push_back({l,r,i});
}
for(int t = 0;t <= n;t++) {
for(auto [l,r,v,id]:sub[t]) {
t_[id].upd(l,r,v);
}
for(auto [l,r,i]:qr[t]) {
ans[i] = t_[0].get(l-t,r-t) + t_[1].get(l,r);
}
}
for(int i = 1;i <= q;++i) {
cout << ans[i] << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int t = 1;
// cin >> t;
while(t--) {
test();
}
}
