#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct Fenwick {
int n;
vector<i64> val, inc;
Fenwick(int n) : n(n) {
val.assign(n, 0);
inc.assign(n, 0);
}
void update(int i, int w, int v, int t) {
for (; i < n; i |= (i + 1)) {
val[i] += t * (w - v);
inc[i] += (v - w);
}
}
i64 query(int i, int t) {
i64 res = 0;
for (; i >= 0; i = (i & (i + 1)) - 1) {
res += val[i] + inc[i] * t;
}
return res;
}
i64 get(int l, int r, int t) {
return query(r, t) - query(l - 1, t);
}
};
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);
Fenwick bit(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 += bit.get(0, index - 1, t);
res += (index ? pref[index - 1] : 0);
return res;
};
vector<int> was(n);
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);
bit.update(i, was[i], dif, t);
was[i] = dif;
}
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;
}
