#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n,q,sn,of;
ll M = 200'050;
struct SegmentTree {
ll n, base;
vector<ll> tree, lazy;
SegmentTree(ll _n) {
n = _n;
ll lvl = ceil(log2(double(n+1)));
base = 1<<lvl;
tree.assign(2*base, 0);
lazy.assign(2*base, 0);
}
void update(ll p, ll k, ll val) {
Update(1, 0, base-1, p, k, val);
}
ll query(ll p, ll k) {
return Query(1, 0, base-1, p, k);
}
void push(ll v, ll a, ll b) {
if(!lazy[v] || a==b) return;
ll l = 2*v; ll r = l+1;
ll len = (b-a+1)/2;
tree[l] += len*lazy[v];
tree[r] += len*lazy[v];
lazy[l] += lazy[v];
lazy[r] += lazy[v];
lazy[v] = 0;
}
void Update(ll v, ll a, ll b, ll p, ll k, ll val) {
if(b<p || k<a) return;
if(p<=a && b<=k) {
tree[v] += (b-a+1)*val;
lazy[v] += val;
return;
}
ll l = 2*v; ll r = l+1; ll mid = (a+b)/2;
push(v, a, b);
Update(l, a, mid, p,k,val);
Update(r, mid+1, b, p,k,val);
tree[v] = tree[l] + tree[r];
}
ll Query(ll v, ll a, ll b, ll p, ll k) {
if(b<p || k<a) return 0;
if(p<=a && b<=k) return tree[v];
ll l = 2*v; ll r = l+1; ll mid = (a+b)/2;
push(v, a, b);
return Query(l, a, mid, p,k) + Query(r, mid+1, b, p,k);
}
};
struct query {
ll l,r,x,i;
void use(vector<SegmentTree> &s) {
s[i].update(l, r, x);
}
};
vector<vector<query>> events(4*M);
void add_triangle(ll i, ll w, ll x) {
query q1_s = {i+w+of, sn-1, -x, 0};
query q1_e = q1_s; q1_e.x *= -1;
query q2_s = {i-1+of, sn-1, x, 1};
query q2_e = q2_s; q2_e.x *= -1;
events[1].push_back(q1_s); events[1].push_back(q2_s);
events[w+1].push_back(q1_e); events[w+1].push_back(q2_e);
}
void add_rownoleglobok(ll i, ll wys, ll dl, ll x) {
add_triangle(i+1, dl-1, -x);
add_triangle(i-wys+1, wys-1, -x);
add_triangle(i-wys+1, wys+dl-1, x);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> q;
sn = 3*n+50;
of = 3*n / 2 + 50;
vector<SegmentTree> s(2, SegmentTree(sn));
vector<ll> a(n);
for(ll i=0; i<n; ++i) cin >> a[i];
vector<ll> ans(q, 0);
vector<pair<ll, ll>> queries;
vector<vector<ll>> buckets(n+2);
for(ll i=0; i<q; ++i) {
ll l,r,t;
cin >> t >> l >> r;
++t;
queries.emplace_back(l,r);
buckets[t].push_back(i);
}
stack<ll> stos;
vector<ll> left(n, -1), right(n, -1);
for(ll i=0; i<n; ++i) {
while(stos.size() && a[stos.top()] < a[i]) stos.pop();
if(stos.size()) left[i] = stos.top();
stos.push(i);
}
while(stos.size()) stos.pop();
for(ll i=n-1; i>=0; --i) {
while(stos.size() && a[stos.top()] <= a[i]) stos.pop();
if(stos.size()) right[i] = stos.top();
stos.push(i);
}
for(ll i=0; i<n; ++i) {
add_rownoleglobok(i+1, (left[i]==-1 ? n+2 : i-left[i]), (right[i]==-1 ? n+2 : right[i]-i), a[i]);
}
for(ll t=1; t<=n+1; ++t) {
for(auto &x : events[t]) x.use(s);
for(auto i : buckets[t]) {
auto[l, r] = queries[i];
ans[i] = s[0].query(l+of, r+of) + s[1].query(l-t+of, r-t+of);
}
}
for(ll i=0; i<q; ++i) cout << ans[i] << "\n";
return 0;
}
