// coached by rainboy
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 200000;
const int Q = 200000;
const int N_ = 1 << 18;
int aa[N], qu[N], pp[N], qq[N];
int tt_[Q], ll_[Q], rr_[Q], zz[Q]; long long xx[Q];
int tt[N * 7], ll[N * 7], rr[N * 7], bb[N * 7], hh[N * 7];
long long st[2][N_ << 1], lz[2][N_]; int sz[N_ << 1], h_, n_;
void put(int z, int i, long long a) {
st[z][i] += a * sz[i];
if (i < n_)
lz[z][i] += a;
}
void pus(int z, int i) {
if (lz[z][i]) {
int l = i << 1, r = l ^ 1;
put(z, l, lz[z][i]);
put(z, r, lz[z][i]);
lz[z][i] = 0;
}
}
void pul(int z, int i) {
if (!lz[z][i]) {
int l = i << 1, r = l ^ 1;
st[z][i] = st[z][l] + st[z][r];
}
}
void push(int z, int i) {
for (int h = h_; h; h--)
pus(z, i >> h);
}
void pull(int z, int i) {
while (i >>= 1)
pul(z, i);
}
void build(int n) {
for (h_ = 0, n_ = 1; n_ < n; h_++, n_ <<= 1)
;
for (int i = 0; i < n_; i++)
sz[i + n_] = 1;
for (int i = n_ - 1; i; i--)
sz[i] = sz[i << 1] << 1;
}
void update(int z, int l, int r, int a) {
int l_ = l += n_, r_ = r += n_;
push(z, l_), push(z, r_);
for ( ; l <= r; l >>= 1, r >>= 1) {
if (l & 1)
put(z, l++, a);
if (!(r & 1))
put(z, r--, a);
}
pull(z, l_), pull(z, r_);
}
long long query(int z, int l, int r) {
long long a = 0;
push(z, l += n_), push(z, r += n_);
for ( ; l <= r; l >>= 1, r >>= 1) {
if (l & 1)
a += st[z][l++];
if (!(r & 1))
a += st[z][r--];
}
return a;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
int n, q; cin >> n >> q;
for (int i = 0; i < n; i++)
cin >> aa[i];
for (int z = 0; z < q; z++)
cin >> tt_[z] >> ll_[z] >> rr_[z], ll_[z]--, rr_[z]--, zz[z] = z;
sort(zz, zz + q, [] (int z0, int z1) { return tt_[z0] < tt_[z1]; });
for (int cnt = 0, i = 0; i < n; i++) {
while (cnt && aa[qu[cnt - 1]] <= aa[i])
cnt--;
pp[i] = cnt ? qu[cnt - 1] : -1, qu[cnt++] = i;
}
for (int cnt = 0, i = n - 1; i >= 0; i--) {
while (cnt && aa[qu[cnt - 1]] < aa[i])
cnt--;
qq[i] = cnt ? qu[cnt - 1] : n, qu[cnt++] = i;
}
int m = 0; build(n);
for (int i = 0; i < n; i++) {
int a = aa[i], p = pp[i], q = qq[i];
update(0, i, q - 1, a);
if (p != -1) {
tt[m] = q - p - 1, ll[m] = i, rr[m] = q - 1, bb[m] = -a, hh[m] = m, m++;
tt[m] = i - p, ll[m] = -1, rr[m] = p, bb[m] = -a, hh[m] = m, m++;
tt[m] = q - p - 1, ll[m] = -1, rr[m] = p, bb[m] = a, hh[m] = m, m++;
tt[m] = i - p, ll[m] = 0, rr[m] = i - 1, bb[m] = a, hh[m] = m, m++;
tt[m] = q - p - 1, ll[m] = 0, rr[m] = i - 1, bb[m] = -a, hh[m] = m, m++;
}
if (i + 1 < q) {
update(1, i + 1, n - 1, -a);
tt[m] = q - i - 1, ll[m] = i + 1, rr[m] = -1, bb[m] = a, hh[m] = m, m++;
if (q < n) {
update(0, q, n - 1, a);
tt[m] = q - i - 1, ll[m] = q, rr[m] = n - 1, bb[m] = -a, hh[m] = m, m++;
}
}
}
sort(hh, hh + m, [] (int h0, int h1) { return tt[h0] < tt[h1]; });
long long s = 0;
for (int g = 0, y = 0; y < q; y++) {
int z = zz[y], t_ = tt_[z], l_ = ll_[z], r_ = rr_[z];
for (int h; g < m && tt[h = hh[g]] <= t_; g++) {
int l = ll[h], r = rr[h], a = bb[h];
if (l == -1)
update(1, 0, r, a), s += a;
else if (r == -1)
update(1, l, n - 1, a);
else
update(0, l, r, a);
}
xx[z] = query(0, l_, r_);
if (r_ < t_)
xx[z] += s * (r_ - l_ + 1);
else if (l_ < t_)
xx[z] += s * (t_ - l_) + query(1, 0, r_ - t_);
else
xx[z] += query(1, l_ - t_, r_ - t_);
}
for (int z = 0; z < q; z++)
cout << xx[z] << '\n';
return 0;
}
