#include <bits/stdc++.h>
using namespace std;
template<typename T>
struct Fenwick {
vector<T> t;
int n;
Fenwick(int x) {
n = x;
t.assign(x + 1, 0);
}
Fenwick() = default;
T get(int i) {
T ans = 0;
for (; i > 0; i -= i & -i)
ans += t[i];
return ans;
}
//[l, r)
T get(int l, int r) {
return get(r - 1) - get(l - 1);
}
void modify(int i, T v) {
assert(i > 0);
for (; i <= n; i += i & -i)
t[i] += v;
}
};
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> s(n + 1);
vector<ll> ans(q);
vector<array<int, 3>> queries[n + 1];
for (int i = 1; i <= n; ++i) {
cin >> s[i];
}
for (int i = 0; i < q; ++i) {
int t, l, r;
cin >> t >> l >> r;
queries[l - 1].push_back({t, -1, i});
queries[r].push_back({t, 1, i});
}
Fenwick<ll> add_l(n), add_q(n), sub_l(n), sub_q(n);
vector<int> stk;
ll pref = 0;
for (int i = 1; i <= n; ++i) {
auto upd = [&](int len, ll k) {
add_l.modify(i - len, k);
add_q.modify(i - len, k * (n - i + len));
if (len > 1) {
sub_l.modify(len - 1, k);
sub_q.modify(len - 1, (len - 1) * k);
}
};
while (!stk.empty() && s[stk.back()] <= s[i]) {
int b = stk.back();
stk.pop_back();
if (!stk.empty()) {
upd(i - stk.back(), s[b] - s[stk.back()]);
}
}
if (!stk.empty()) {
upd(i - stk.back(), s[stk.back()] - s[i]);
}
stk.push_back(i);
pref += s[i];
for (auto [len, k, idx]: queries[i]) {
ll sum = pref;
sum += add_q.get(i - len + 1, i + 1) - (n - i) * (add_l.get(i - len + 1, i + 1));
sum += len * (add_l.get(i - len) - (sub_l.get(n) - sub_l.get(len)));
sum -= sub_q.get(len);
ans[idx] += sum * k;
}
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << '\n';
}
return 0;
}
