#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif
const int N = 2e5 + 5;
struct segtree {
int n;
vector<long long> seg, lazy;
segtree() {
n = N * 3;
seg.resize(n * 2);
lazy.resize(n * 2);
}
void push(int nd, int l, int r) {
if (!lazy[nd]) {
return;
}
seg[nd] += lazy[nd] * (r - l + 1);
if (l != r) {
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
lazy[nd + 1] += lazy[nd];
lazy[rs] += lazy[nd];
}
lazy[nd] = 0;
}
void upd(int nd, int l, int r, int s, int e, int v) {
push(nd, l, r);
if (l >= s && r <= e) {
lazy[nd] = v;
push(nd, l, r);
return;
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (mid >= e) {
upd(nd + 1, l, mid, s, e, v);
push(rs, mid + 1, r);
} else {
if (mid < s) {
upd(rs, mid + 1, r, s, e, v);
push(nd + 1, l, mid);
} else {
upd(nd + 1, l, mid, s, e, v);
upd(rs, mid + 1, r, s, e, v);
}
}
seg[nd] = seg[nd + 1] + seg[rs];
}
void upd(int s, int e, int v) {
if (s <= e) {
s += N, e += N;
upd(0, 0, n - 1, s, e, v);
}
}
long long qry(int nd, int l, int r, int s, int e) {
push(nd, l, r);
if (l >= s && r <= e) {
return seg[nd];
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (mid >= e) {
return qry(nd + 1, l, mid, s, e);
} else {
if (mid < s) {
return qry(rs, mid + 1, r, s, e);
} else {
return qry(nd + 1, l, mid, s, e) + qry(rs, mid + 1, r, s, e);
}
}
}
long long qry(int s, int e) {
s += N, e += N;
return qry(0, 0, n - 1, s, e);
}
};
int n, q;
int a[N];
segtree one, two;
long long ans[N];
int pre[N], nxt[N];
vector<array<int, 3>> qt[N];
vector<array<int, 3>> rev[N];
void triangle(int l, int r, int v) {
if (l > r) return;
one.upd(l, n + n, v); //[-n, 2n] --> [0, 3n] (size = 6N)
two.upd(r + 1, n, -v); //[2, n] --> [2 + n, 2n] (size = 4N)
if (r - l + 1 <= n) {
rev[r - l + 1].push_back({l, r, v});
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
stack<int> stk;
for (int i = 1; i <= n; ++i) {
while (!stk.empty() && a[stk.top()] <= a[i]) {
stk.pop();
}
if (stk.empty()) {
pre[i] = -n;
} else {
pre[i] = stk.top();
}
stk.push(i);
}
while (!stk.empty()) {
stk.pop();
}
for (int i = n; i >= 1; --i) {
while (!stk.empty() && a[stk.top()] < a[i]) {
stk.pop();
}
if (stk.empty()) {
nxt[i] = n + 1;
} else {
nxt[i] = stk.top();
}
stk.push(i);
}
for (int i = 1; i <= n; ++i) {
triangle(pre[i] + 1, nxt[i] - 1, a[i]);
triangle(pre[i] + 1, i - 1, -a[i]);
triangle(i + 1, nxt[i] - 1, -a[i]);
}
for (int i = 1; i <= q; ++i) {
int t, l, r;
cin >> t >> l >> r;
qt[t].push_back({l, r, i});
}
for (int t = 1; t <= n; ++t) {
for (auto [l, r, v] : rev[t]) {
one.upd(l, n + n, -v);
two.upd(r + 1, n, v);
}
for (auto [l, r, i] : qt[t]) {
ans[i] = one.qry(l - t, r - t) + two.qry(l, r);
}
}
for (int i = 1; i <= q; ++i) {
cout << ans[i] << '\n';
}
return 0;
}
