#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define rep(i, a, b) for (auto i = (a); i <= (b); ++i)
#define trav(x, v) for (auto &x : v)
#define eb(x...) emplace_back(x)
#define all(x) begin(x), end(x)
#define lb(x...) lower_bound(x)
using ll = int64_t;
struct S {
int n; vector<ll> t;
S(int n = 0) : n{n}, t(2 * n, 0) { }
ll query(int r) {
ll s = 0; int l = n;
for (r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) s += t[l++];
if (r & 1) s += t[--r];
}
return s;
}
void add(int p, ll v) {
for (t[p += n] += v; p >>= 1; )
t[p] = t[p << 1|0] + t[p << 1|1];
}
};
const int N = 13 << 14;
int s[N], p[N], nxt[N], t[N];
ll ans[N], pref[N];
vector<int> e[N], g[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
rep(i, 1, n) {
cin >> s[i];
pref[i] = pref[i - 1] + s[i];
p[i] = i - 1; nxt[i] = n + 1;
while (p[i] && s[p[i]] < s[i])
nxt[p[i]] = i, p[i] = p[p[i]];
}
rep(i, 1, n) if (!p[i]) p[i] = i;
rep(i, 1, m) {
int l, r; cin >> t[i] >> l >> r;
e[l - 1].eb(-i); e[r].eb(i);
}
vector<int> a;
rep(i, 1, n) {
while(!a.empty() && s[a.back()] < s[i]) a.pop_back();
a.eb(i);
trav(j, e[i]) {
int prev = *lb(all(a), i - t[abs(j)]);
ll del = 1ll * s[prev] * (i - prev) + pref[prev];
if (j < 0) ans[-j] -= del;
else ans[j] += del;
g[prev].eb(j);
}
}
S U(n), US(n), D(n), DS(n);
rep(i, 1, n) {
ll w = s[p[i]] - s[i];
int u = i - p[i] - 1, d = nxt[i] - p[i] - 1;
US.add(u, w * u); U.add(u, w);
DS.add(d, w * d); D.add(d, w);
trav(j, g[i]) {
int t = ::t[abs(j)];
ll del = 0;
del += U.query(t) * t - US.query(t);
del += DS.query(t) - D.query(t) * t;
if (j < 0) ans[-j] -= del;
else ans[j] += del;
}
}
rep(i, 1, m) cout << ans[i] << '\n';
}
