#include <bits/stdc++.h>
using namespace std;
const int N = 200001;
struct fenwick {
vector<long long> tree;
int n;
fenwick(int n) : tree(n + 1), n(n) {}
void update(int a, long long x) {
for ( ; a <= n; a += a & -a) {
tree[a] += x;
}
}
long long query(int a) {
long long sum = 0;
for ( ; a > 0; a -= a & -a) {
sum += tree[a];
}
return sum;
}
};
vector<array<long long, 3>> queries[N];
vector<array<long long, 2>> updates[N];
long long s[N], ans[N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
}
for (int i = 1; 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});
}
vector<int> stack;
for (int i = 1; i <= n; ++i) {
while (!stack.empty() && s[stack.back()] <= s[i]) {
int j = stack.back();
stack.pop_back();
if (!stack.empty()) {
int k = stack.back();
updates[i].push_back({i - k, s[j] - s[k]});
}
}
if (!stack.empty()) {
int j = stack.back();
updates[i].push_back({i - j, s[j] - s[i]});
}
stack.push_back(i);
}
long long prefix = 0;
fenwick add_q(n), add_l(n), sub_q(n), sub_l(n);
for (int i = 1; i <= n; ++i) {
for (auto [j, k] : updates[i]) {
add_l.update(i - j, k);
add_q.update(i - j, (n - i + j) * k);
if (j > 1) {
sub_l.update(j - 1, k);
sub_q.update(j - 1, (j - 1) * k);
}
}
prefix += s[i];
for (auto [j, k, l] : queries[i]) {
long long sum = prefix;
sum += add_q.query(i) - add_q.query(i - j);
sum -= (n - i) * (add_l.query(i) - add_l.query(i - j));
sum += j * add_l.query(i - j);
sum -= sub_q.query(j);
sum -= j * (sub_l.query(n) - sub_l.query(j));
ans[l] += k * sum;
}
}
for (int i = 1; i <= q; ++i) {
cout << ans[i] << "\n";
}
}
