// Solution:
//
// Draw a grid, with rows as time and columns as index. For each original S,
// it must for a parallelogram. Each parallelogram can be decomposed into
// triangles. Each triangle can be stored in 2 Dat Structures that support
// range add and range query, where 1 stores diagonals and the other stores
// the vertical aspect. For the diagonal, we can shift query ranges to the
// left, leaving a rectangular one as well. This can be done using a segment
// tree or 2 fenwick trees, each.
#include <bits/stdc++.h>
using namespace std;
class Fenwick {
private:
int sz;
vector<long long> tree;
public:
Fenwick() {}
Fenwick(int sz) : sz(sz) {
tree.assign(sz, 0);
}
void Update(int p, long long x) {
p += sz / 2;
for (int i = p; i < sz; i |= i + 1) {
tree[i] += x;
}
}
long long Query(int p) {
p += sz / 2;
long long res = 0;
for (int i = p + 1; i > 0; i &= i - 1) {
res += tree[i - 1];
}
return res;
}
};
const int MAXN = 400005;
int N, Q;
int S[MAXN];
int L[MAXN], R[MAXN];
vector<array<int, 3>> query[MAXN];
long long ans[MAXN];
Fenwick start_pref(2 * MAXN);
Fenwick start_const(2 * MAXN);
Fenwick end_pref(2 * MAXN);
Fenwick end_const(2 * MAXN);
vector<array<int, 3>> update[MAXN];
void AddTriangle(int l, int r, int v) {
if (l > r) return;
update[0].push_back({l, r, v});
update[r - l + 1].push_back({l, r, -v});
}
void Update(int t) {
for (auto u : update[t]) {
int l, r, v;
l = u[0], r = u[1], v = u[2];
start_pref.Update(l, v);
start_const.Update(l, 1ll * v * (l - 1));
end_pref.Update(r + 1, -v);
end_const.Update(r + 1, -1ll * v * r);
}
}
long long Query(int t, int r) {
long long start_ = 1ll * (r - t) * start_pref.Query(r - t) - start_const.Query(r - t); // shift to the left
long long end_ = 1ll * r * end_pref.Query(r) - end_const.Query(r);
return start_ + end_;
}
long long Query(int t, int l, int r) {
return Query(t, r) - Query(t, l - 1);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> N >> Q;
for (int i = 1; i <= N; i++) {
cin >> S[i];
L[i] = - N - 1;
R[i] = + N + 1;
}
vector<int> st;
for (int i = 1; i <= N; i++) {
while (!st.empty() && S[st.back()] <= S[i]) {
st.pop_back();
}
if (!st.empty()) {
L[i] = st.back();
}
st.emplace_back(i);
}
st.clear();
for (int i = N; i >= 1; i--) {
while (!st.empty() && S[st.back()] < S[i]) {
st.pop_back();
}
if (!st.empty()) {
R[i] = st.back();
}
st.emplace_back(i);
}
for (int i = 1; i <= N; i++) {
AddTriangle(L[i] + 1, R[i] - 1, S[i]);
AddTriangle(L[i] + 1, i - 1, -S[i]);
AddTriangle(i + 1, R[i] - 1, -S[i]);
}
for (int i = 0; i < Q; i++) {
int t, l, r;
cin >> t >> l >> r;
query[t].push_back({l, r, i});
}
for (int t = 0; t <= N; t++) {
Update(t);
for (auto &q : query[t]) {
ans[q[2]] = Query(t, q[0], q[1]);
}
}
for (int i = 0; i < Q; i++) {
cout << ans[i] << "\n";
}
return 0;
}
