#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct SegmentTree {
int n;
vector<i64> val, inc;
SegmentTree(int n) : n(n) {
val.assign(4 * n, 0);
inc.assign(4 * n, 0);
}
void update(int i, int v, int t) {
update(i, v, t, 0, 0, n - 1);
}
void update(int i, int v, int t, int x, int lx, int rx) {
if (lx == rx) {
val[x] += inc[x] * t;
inc[x] = v;
val[x] -= inc[x] * t;
return;
}
int mid = (lx + rx) / 2;
if (i <= mid) {
update(i, v, t, 2 * x + 1, lx, mid);
} else {
update(i, v, t, 2 * x + 2, mid + 1, rx);
}
val[x] = val[2 * x + 1] + val[2 * x + 2];
inc[x] = inc[2 * x + 1] + inc[2 * x + 2];
}
i64 get(int l, int r, int t) {
return get(l, r, t, 0, 0, n - 1);
}
i64 get(int l, int r, int t, int x, int lx, int rx) {
if (lx > r || rx < l) {
return 0;
}
if (l <= lx && rx <= r) {
return val[x] + inc[x] * t;
}
int mid = (lx + rx) / 2;
return get(l, r, t, 2 * x + 1, lx, mid) + get(l, r, t, 2 * x + 2, mid + 1, rx);
}
};
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int const lg = 20;
vector<i64> pref(n);
vector<vector<pair<int, int>>> sparse(n, vector<pair<int, int>>(lg));
for (int i = 0; i < n; ++i) {
sparse[i][0] = {a[i], i};
pref[i] = a[i] + (i ? pref[i - 1] : 0);
}
for (int j = 1; j < lg; ++j) {
for (int i = 0; i < n; ++i) {
int ni = min(n - 1, i + (1 << (j - 1)));
sparse[i][j] = max(sparse[i][j - 1], sparse[ni][j - 1]);
}
}
vector<int> t(q), l(q), r(q);
for (int i = 0; i < q; ++i) {
cin >> t[i] >> l[i] >> r[i];
--l[i], --r[i];
t[i] = min(t[i], n - 1);
}
vector<vector<int>> queries(n);
for (int i = 0; i < q; ++i) {
queries[t[i]].push_back(i);
}
vector<int> stk;
vector<vector<int>> update(n);
for (int i = n - 1; i >= 0; --i) {
while (stk.size() && a[i] > a[stk.back()]) {
update[stk.back() - i - 1].push_back(i);
stk.pop_back();
}
int nxt = (stk.size() ? stk.back() : n);
update[nxt - i - 1].push_back(i);
stk.push_back(i);
}
vector<i64> ans(q);
SegmentTree st(n);
auto query = [&](int l, int r, int t) -> i64 {
if (l > r) {
return 0;
}
i64 res = 0;
t = min(t, r);
int d = __lg(t + 1);
auto [mx, index] = max(sparse[r - t][d], sparse[r - (1 << d) + 1][d]);
res = 1LL * mx * (r - index + 1);
res += st.get(0, index - 1, t);
res += (index ? pref[index - 1] : 0);
return res;
};
for (int t = 0; t < n; ++t) {
for (auto i : update[t]) {
int dif = (i + t + 1 < n && a[i + t + 1] < a[i] ? a[i] - a[i + t + 1] : 0);
st.update(i, dif, t);
}
for (auto i : queries[t]) {
ans[i] = query(0, r[i], t) - query(0, l[i] - 1, t);
}
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
