#define taskname ""
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct FenwickTree {
int n;
vector<pair<ll, ll>> bit;
FenwickTree() {}
FenwickTree(int _n) : n(_n) {
bit.resize(n + 1, {0, 0});
}
void Update(int pos, pair<ll, ll> val) {
for (int i = pos; i <= n; i += i & (-i)) {
bit[i].first += val.first;
bit[i].second += val.second;
}
}
pair<ll, ll> PrefixSum(int pos) {
pair<ll, ll> sum = {0, 0};
for (int i = pos; i > 0; i -= i & (-i)) {
sum.first += bit[i].first;
sum.second += bit[i].second;
}
return sum;
}
pair<ll, ll> RangeSum(int l, int r) {
pair<ll, ll> x = PrefixSum(r);
pair<ll, ll> y = PrefixSum(l - 1);
return {x.first - y.first, x.second - y.second};
}
} bit1, bit2;
int main() {
if (fopen(taskname".inp", "r")) {
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> s(n + 1);
for (int i = 1; i <= n; i++) {
cin >> s[i];
}
vector<int> l(n + 1), r(n + 1);
stack<int> a;
for (int i = 1; i <= n; i++) {
while (!a.empty() && s[a.top()] <= s[i]) {
a.pop();
}
l[i] = (a.empty() ? 1 : a.top() + 1);
a.push(i);
}
stack<int> b;
for (int i = n; i >= 1; i--) {
while (!b.empty() && s[b.top()] < s[i]) {
b.pop();
}
r[i] = (b.empty() ? n : b.top() - 1);
b.push(i);
}
vector<pair<pair<int, int>, int>> h1;
vector<int> c;
for (int i = 1; i <= n; i++) {
c.push_back(i);
h1.push_back({{i, 0}, s[i]});
h1.push_back({{r[i] + 1, r[i] + 1 - i}, -s[i]});
if (l[i] > 1) {
c.push_back(l[i] - 1);
h1.push_back({{i, i - l[i] + 1}, -s[i]});
h1.push_back({{r[i] + 1, r[i] + 2 - l[i]}, s[i]});
}
}
vector<pair<pair<int, int>, int>> h2 = h1;
sort(h1.begin(), h1.end());
sort(h2.begin(), h2.end(), [](pair<pair<int, int>, int> x, pair<pair<int, int>, int> y) {
return x.first.second < y.first.second;
});
sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());
vector<ll> result(q + 1, 0);
vector<pair<pair<pair<int, int>, int>, int>> u, v;
for (int i = 1; i <= q; i++) {
int t, l, r;
cin >> t >> l >> r;
u.push_back({{{r, r - t}, i}, 1});
u.push_back({{{l - 1, l - t - 1}, i}, -1});
v.push_back({{{t, r - t}, i}, 1});
v.push_back({{{t, l - t - 1}, i}, -1});
}
sort(u.begin(), u.end());
int j = -1;
bit1 = FenwickTree(c.size());
for (auto i : u) {
while (j + 1 < h1.size() && h1[j + 1].first.first <= i.first.first.first) {
j++;
int x = upper_bound(c.begin(), c.end(), h1[j].first.first - h1[j].first.second) - c.begin();
bit1.Update(x, { 1LL * (1 - h1[j].first.first) * h1[j].second, h1[j].second });
}
int y = lower_bound(c.begin(), c.end(), i.first.first.second) - c.begin() + 1;
pair<ll, ll> z = bit1.RangeSum(y, c.size());
result[i.first.second] += i.second * (z.first + z.second * i.first.first.first);
}
sort(v.begin(), v.end());
j = -1;
bit2 = FenwickTree(c.size());
for (auto i : v) {
while (j + 1 < h2.size() && h2[j + 1].first.second <= i.first.first.first) {
j++;
int x = upper_bound(c.begin(), c.end(), h2[j].first.first - h2[j].first.second) - c.begin();
bit2.Update(x, { 1LL * (1 - h2[j].first.second) * h2[j].second, h2[j].second });
}
int y = lower_bound(c.begin(), c.end(), i.first.first.second) - c.begin();
pair<ll, ll> z = bit2.RangeSum(1, y);
result[i.first.second] += i.second * (z.first + z.second * i.first.first.first);
}
for (int i = 1; i <= q; i++) {
cout << result[i] << '\n';
}
return 0;
}
