#include <bits/stdc++.h>
#define fs first
#define se second
using namespace std;
typedef long long llong;
typedef pair<int, int> pii;
struct fenwick {
static const int N = 200005;
llong fen[N + N + 5];
void init() {
memset(fen, 0, sizeof(fen));
}
void update(int i, llong x) {
i += N;
while (i <= N + N) {
fen[i] += x;
i += i & -i;
}
}
llong query(int i) const {
i += N;
llong ret = 0;
while (i) {
ret += fen[i];
i -= i & -i;
}
return ret;
}
} fen1, fen2;
int n, q;
int S[200001];
pii seg[1 << 19];
void init(int i, int s, int e) {
if (s == e) {
seg[i] = pii(S[s], s);
return;
}
int m = (s + e) / 2;
init(i + i, s, m);
init(i + i + 1, m + 1, e);
seg[i] = max(seg[i + i], seg[i + i + 1]);
}
pii query(int i, int s, int e, int x, int y) {
if (e < x || y < s) return pii(0, 0);
if (x <= s && e <= y) return seg[i];
int m = (s + e) / 2;
return max(query(i + i, s, m, x, y), query(i + i + 1, m + 1, e, x, y));
}
vector<pair<pii, int>> U;
void solve(int s, int e) {
if (s > e) return;
int m = query(1, 1, n, s, e).se;
if (s > 1) {
U.emplace_back(pii(m, m - s + 1), -S[m]);
U.emplace_back(pii(e + 1, e - s + 2), S[m]);
}
{
U.emplace_back(pii(m, 0), S[m]);
U.emplace_back(pii(e + 1, e - m + 1), -S[m]);
}
solve(s, m - 1);
solve(m + 1, e);
}
llong ans[200001];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> S[i];
init(1, 1, n);
solve(1, n);
vector<pair<pii, int>> Q;
for (int i = 1; i <= q; ++i) {
int t, l, r;
cin >> t >> l >> r;
Q.emplace_back(pii(r, t), i);
Q.emplace_back(pii(l - 1, t), -i);
}
for (int it = 0; it < 2; ++it) {
sort(U.begin(), U.end());
sort(Q.begin(), Q.end());
fen1.init();
fen2.init();
for (int i = 0, j = 0; i < int(Q.size()); ++i) {
while (j < int(U.size()) && U[j].fs.fs <= Q[i].fs.fs) {
int jx = U[j].fs.se - U[j].fs.fs;
fen1.update(jx, U[j].se);
fen2.update(jx, U[j].se * (1ll - U[j].fs.fs));
++j;
}
int ix = Q[i].fs.se - Q[i].fs.fs - it;
llong val = fen1.query(ix) * Q[i].fs.fs + fen2.query(ix);
if (Q[i].se < 0) ans[-Q[i].se] -= val;
else ans[Q[i].se] += val;
}
for (auto &i : U) swap(i.fs.fs, i.fs.se);
for (auto &i : Q) swap(i.fs.fs, i.fs.se);
}
for (int i = 1; i <= q; ++i) printf("%lld\n", ans[i]);
return 0;
}
