#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 2e5 + 5;
int n, q;
int a[N], lt[N];
long long res[N];
vector<array<int, 3>> events[N], Queries[N];
struct Fenwick {
long long s[2 * N];
void upd(int i, long long x) {
for (; i <= 2 * n; i += i & -i) {
s[i] += x;
}
}
long long qry(int i) {
long long res = 0;
for (; i; i -= i & -i) {
res += s[i];
}
return res;
}
} ft[4];
void upd(int l, int r, int x) {
ft[0].upd(l, x);
ft[1].upd(r + 1, -x);
ft[2].upd(l, (long long) (1 - l) * x);
ft[3].upd(r + 1, (long long) r * x);
}
long long qry(int i, int t) {
i += n;
auto A = ft[0].qry(i - t), B = ft[1].qry(i), C = ft[2].qry(i - t), D = ft[3].qry(i);
return (A + B) * (i - t) + C + D + B * t;
}
void add(int l, int r, int h, int x) {
l += n, r += n;
events[0].push_back({l, r, x});
if (h <= n) {
events[h].push_back({l, r, -x});
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= q; ++i) {
int l, r, t; cin >> t >> l >> r;
Queries[t].push_back({l, r, i});
}
vector<int> st = {-n};
for (int i = 1; i <= n; ++i) {
while (st.size() > 1 && a[st.back()] <= a[i]) {
st.pop_back();
}
lt[i] = st.back();
st.push_back(i);
}
st.clear();
st.push_back(n + 1);
for (int i = n; i > 0; --i) {
while (st.size() > 1 && a[st.back()] < a[i]) {
st.pop_back();
}
int r = st.back();
if (lt[i] + 1 < i) {
add(lt[i] + 1, i - 1, i - lt[i] - 1, -a[i]);
}
if (i < r - 1) {
add(i + 1, r - 1, r - i - 1, -a[i]);
}
add(lt[i] + 1, r - 1, r - lt[i] - 1, a[i]);
st.push_back(i);
}
for (int t = 0; t <= n; ++t) {
for (auto [l, r, x] : events[t]) {
upd(l, r, x);
}
for (auto [l, r, id] : Queries[t]) {
res[id] = qry(r, t) - qry(l - 1, t);
}
}
for (int i = 1; i <= q; ++i) {
cout << res[i] << "\n";
}
return 0;
}
