//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif
struct pytanie {
int l, r, id;
};
struct SegTree {
struct node {
long long A, B;
};
vector<node> st;
int com;
SegTree(int n) {
com = 1;
while (com < n) {
com <<= 1;
}
st.resize(com << 1);
--com;
}
void wstaw(int x, long long A, long long B) {
x += com;
st[x] = {A, B};
x >>= 1;
while (x) {
st[x] = {st[x * 2].A + st[x * 2 + 1].A, st[x * 2].B + st[x * 2 + 1].B};
x >>= 1;
}
}
long long pytaj(int a, int b, int tm) {
a += com;
b += com + 1;
long long ret = 0;
while (a < b) {
if (a & 1) {
ret += st[a].A * tm + st[a].B;
++a;
}
if (b & 1) {
ret += st[b - 1].A * tm + st[b - 1].B;
}
a >>= 1;
b >>= 1;
}
return ret;
}
};
struct nod {
int lf, rg;
};
//~ const int N = 100;
const int N = 201000;
int n, q, com;
int t[N];
int lf[N]; // następny na lewo większy
int rg[N]; // następny na prawo większy równy
int slp[N]; // aktualny slope
long long odp[N];
vector<pytanie> pyt[N]; // zapytania po czasie
vector<int> zgon[N]; // kto właśnie znika
vector<int> slope[N]; // komu maleje slope w tym momencie
vector<nod> ts;
int kiedy_zgon(int x) { // pierwszy moment nieistnienia x
if (lf[x] == 0) {
return 1e9;
}
return rg[x] - lf[x] - 1;
}
pair<int, int> aktualny(int x, int tm) { // aktualny przedział pożaru x w momencie tm
int l = x;
if (lf[x]) {
l = max(l, lf[x] + tm + 1);
}
int r = min(rg[x] - 1, x + tm);
return {l, r};
}
void update(int x) {
int l = x << 1;
int r = l ^ 1;
ts[x] = {min(ts[l].lf, ts[r].lf), max(ts[l].rg, ts[r].rg)};
}
// pożar, który posiada w sobie p w momencie tm
int fin(int x, int l, int r, int tm, int p) {
if (l == r) {
return l;
}
if (ts[x * 2].lf > ts[x * 2].rg) {
return fin(x * 2 + 1, (l + r) / 2 + 1, r, tm, p);
}
auto lf = aktualny(ts[x * 2].rg, tm);
if (lf.second < p) {
return fin(x * 2 + 1, (l + r) / 2 + 1, r, tm, p);
}
return fin(x * 2, l, (l + r) / 2, tm, p);
}
void zgas(int x) {
x += com;
ts[x] = {(int)1e9, (int)-1e9};
x >>= 1;
while (x) {
update(x);
x >>= 1;
}
}
int main() {
scanf("%d%d", &n, &q);
com = 1;
while (com < n) {
com <<= 1;
}
ts.resize(com << 1);
--com;
SegTree st(n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &t[i]);
st.wstaw(i, t[i], t[i]);
ts[i + com] = {i, i};
slp[i] = 1;
}
for (int i = n + 1; i <= com + 1; ++i) {
ts[i + com] = {(int)1e9, (int)-1e9};
}
for (int i = com; i; --i) {
update(i);
}
t[0] = 1e9 + 7;
t[n + 1] = 1e9 + 7;
for (int i = 1; i <= n; ++i) {
lf[i] = i - 1;
while (t[i] >= t[lf[i]]) {
lf[i] = lf[lf[i]];
}
}
for (int i = n; i; --i) {
rg[i] = i + 1;
while (t[i] > t[rg[i]]) {
rg[i] = rg[rg[i]];
}
}
for (int i = 1; i <= n; ++i) {
int x = kiedy_zgon(i);
//~ debug(i, x);
if (x <= n) {
zgon[x].push_back(i);
}
if (lf[i]) {
slope[i - lf[i] - 1].push_back(i);
}
slope[rg[i] - i - 1].push_back(i);
}
//~ for (int i = 0; i <= n; ++i) {
//~ debug(i, slope[i]);
//~ }
//~ for (int i = 0; i <= n; ++i) {
//~ for (int j = 1; j <= n; ++j) {
//~ debug(i, j, aktualny(j, i));
//~ }
//~ }
for (int i = 1; i <= q; ++i) {
int a, b, c;
scanf("%d%d%d", &c, &a, &b);
pyt[c].push_back({a, b, i});
}
for (int tm = 0; tm <= n; ++tm) {
//~ debug(tm);
for (int i : zgon[tm]) {
//~ debug("ZGON", i);
zgas(i);
st.wstaw(i, 0, 0);
}
for (int i : slope[tm]) {
if (slp[i] == 1) { // zamiana na stały
auto x = aktualny(i, tm);
//~ debug(i, x);
st.wstaw(i, 0, (long long)(x.second - x.first + 1) * t[i]);
}
else { // zamiana na malejący
auto x = aktualny(i, tm);
//~ debug(i, x);
st.wstaw(i, -t[i], (long long)(tm + x.second - x.first + 1) * t[i]);
}
--slp[i];
//~ debug(i, slp[i]);
}
//~ for (int i = 1; i <= n; ++i) {
//~ printf("%lld ", st.pytaj(i, i, tm));
//~ }
//~ printf("\n");
for (auto i : pyt[tm]) {
int poc = fin(1, 1, com + 1, tm, i.l);
int kon = fin(1, 1, com + 1, tm, i.r);
auto p = aktualny(poc, tm);
auto k = aktualny(kon, tm);
//~ debug(i.l, i.r, i.id, poc, kon, p, k);
odp[i.id] = st.pytaj(poc, kon, tm) - (long long)(i.l - p.first) * t[poc] - (long long)(k.second - i.r) * t[kon];
}
}
for (int i = 1; i <= q; ++i) {
printf("%lld\n", odp[i]);
}
return 0;
}
