#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
#ifdef DEBUG
#define debug(args...) _debug(args)
void _debug(const char* format, ...) {
va_list args;
va_start(args, format);
vprintf(format, args);
va_end(args);
}
#else
#define debug(args...)
#endif
#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 400025
#define BUF 200005
struct thing {
int l, r, i;
};
int n, q;
int s[MAXN];
int l[MAXN], r[MAXN];
vector<thing> queries[MAXN], del[MAXN];
ll ans[MAXN];
struct fw {
ll base[MAXN], mult[MAXN];
void nincre(int i, ll x, ll* fw) {
for (; i < MAXN; i += i & -i) fw[i] += x;
}
ll nqsum(int i, ll* fw) {
ll res = 0;
for (; i > 0; i -= i & -i) res += fw[i];
return res;
}
void incre(int i, ll x) {
nincre(i, (1 - i) * x, base);
nincre(i, x, mult);
}
void incre(int s, int e, ll x) {
s += BUF; e += BUF;
incre(s, x);
incre(e + 1, -x);
}
ll qsum(int i) {
return nqsum(i, base) + nqsum(i, mult) * i;
}
ll qsum(int s, int e) {
s += BUF; e += BUF;
return qsum(e) - qsum(s - 1);
}
} par, rect;
void tri(int l, int r, int x, bool todel = 0) {
if (l > r) return;
par.incre(l, n + 1, x);
rect.incre(r + 1, n + 1, x);
if (todel) {
int len = r - l + 1;
if (len <= n) del[len].pb({l, r, -x});
}
}
int main() {
scanf("%d%d", &n, &q);
REP (i, 1, n + 1) {
scanf("%d", &s[i]);
}
REP (i, 0, q) {
int t, l, r; scanf("%d%d%d", &t, &l, &r);
queries[t].pb({l, r, i});
}
vi stk;
REP (i, 1, n + 1) {
while (!stk.empty() && s[stk.back()] <= s[i]) {
stk.pop_back();
}
if (!stk.empty()) {
l[i] = stk.back();
} else {
l[i] = -n;
}
stk.pb(i);
}
stk.clear();
RREP (i, n, 1) {
while (!stk.empty() && s[stk.back()] < s[i]) {
stk.pop_back();
}
if (!stk.empty()) {
r[i] = stk.back();
} else {
r[i] = n + 1;
}
stk.pb(i);
}
REP (i, 1, n + 1) {
tri(l[i] + 1, r[i] - 1, s[i], 1);
tri(l[i] + 1, i - 1, -s[i], 1);
tri(i + 1, r[i] - 1, -s[i], 1);
}
REP (t, 1, n + 1) {
debug("%d\n", t);
#ifdef DEBUG
REP (i, 1, n + 1) {
debug(" %d", par.qsum(i - t, i - t) - rect.qsum(i, i));
}
debug("\n");
#endif
for (thing& o : del[t]) {
auto [l, r, v] = o;
tri(l, r, v);
}
for (thing &o : queries[t]) {
auto [l, r, i] = o;
ans[i] = par.qsum(l - t, r - t) - rect.qsum(l, r);
}
}
REP (i, 0, q) {
printf("%lld\n", ans[i]);
}
return 0;
}
