#include <bits/stdc++.h>
using namespace std;
#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif
#define int long long
const int N = (int) 2e5 + 5;
int n, q;
int a[N], res[N];
vector<pair<int, int>> Q[N];
struct fenwick {
int n;
vector<int> s;
fenwick(int n): n(n) {
s.resize(n);
}
void upd(int i, int x) {
for (; i <= n; i += i & -i) {
s[i - 1] += x;
}
}
int get(int i) {
int res = 0;
for (; i; i -= i & -i) {
res += s[i - 1];
}
return res;
}
};
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef ngu
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
#endif
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= q; ++i) {
int t, l, r;
cin >> t >> l >> r;
Q[r].emplace_back(t, i);
Q[l - 1].emplace_back(t, -i);
}
fenwick ft1(n + 1), ft2(n + 1);
auto upd = [&](int i, int v) {
i++;
ft1.upd(i, v);
ft2.upd(i, -v * (i - 1));
};
auto get = [&](int i) {
i++;
return ft1.get(i) * i + ft2.get(i);
};
vector<int> st, pref;
st.emplace_back(-n);
pref.emplace_back(0);
for (int i = 1; i <= n; ++i) {
while (st.size() && st.back() > 0 && a[st.back()] <= a[i]) {
upd(i - st.back(), -a[st.back()]);
upd(i - st.end()[-2], a[st.back()]);
st.pop_back();
pref.pop_back();
}
upd(0, a[i]);
upd(i - st.back(), -a[i]);
pref.emplace_back(pref.back() + (i - st.back()) * a[i]);
st.emplace_back(i);
for (auto [t, id] : Q[i]) {
int val = get(t);
int p = lower_bound(st.begin(), st.end(), i - t) - st.begin();
val -= (st[p] + t - i) * a[st[p]] + pref.back() - pref[p];
if (id > 0) {
res[id] += val;
} else {
res[-id] -= val;
}
}
}
for (int i = 1; i <= q; ++i) {
cout << res[i] << "\n";
}
}
