#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n,q,sn,of;
ll M = 200'000;
struct SegmentTree {
ll n;
vector<long long> tree, lazy;
SegmentTree(ll _n) {
n = _n;
tree.assign(4 * n, 0);
lazy.assign(4 * n, 0);
}
void build(vector<long long> &arr, ll v, ll tl, ll tr) {
if (tl == tr) {
tree[v] = arr[tl];
} else {
ll tm = (tl + tr) / 2;
build(arr, v * 2, tl, tm);
build(arr, v * 2 + 1, tm + 1, tr);
tree[v] = tree[v * 2] + tree[v * 2 + 1];
}
}
void push(ll v, ll tl, ll tr) {
if (lazy[v] != 0) {
tree[v] += lazy[v] * (tr - tl + 1);
if (tl != tr) {
lazy[v * 2] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
}
lazy[v] = 0;
}
}
void update(ll v, ll tl, ll tr, ll l, ll r, long long addend) {
push(v, tl, tr);
if (l > r) return;
if (l == tl && r == tr) {
lazy[v] += addend;
push(v, tl, tr);
} else {
ll tm = (tl + tr) / 2;
update(v * 2, tl, tm, l, min(r, tm), addend);
update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, addend);
tree[v] = tree[v * 2] + tree[v * 2 + 1];
}
}
long long query(ll v, ll tl, ll tr, ll l, ll r) {
if (l > r) return 0;
push(v, tl, tr);
if (l <= tl && tr <= r) {
return tree[v];
}
ll tm = (tl + tr) / 2;
return query(v * 2, tl, tm, l, min(r, tm))
+ query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
}
};
struct query {
ll l,r,x,i;
void use(vector<SegmentTree> &s) {
s[i].update(1, 0, sn-1, 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 = 5*n+6;
of = 2*n+2;
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(1, 0, sn-1, l+of, r+of) + s[1].query(1, 0, sn-1, l-t+of, r-t+of);
}
}
for(ll i=0; i<q; ++i) cout << ans[i] << "\n";
return 0;
}
