#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }
const int N = 2e5+7;
const int L = 20;
int a[N], t[L][N], lg[N];
vector<array<int, 4>> v;
vector<pair<int, int>> qs[N], add[N];
int get_max(int l, int r) {
int p = lg[r - l + 1];
return max(t[p][l], t[p][r - (1 << p) + 1]);
}
ll get(int t, int x) {
ll ans = 0;
for (auto [l, r, pos, val] : v) {
if (l <= t && t <= r && pos <= x) {
ans += val;
}
}
return ans;
}
ll f[N];
void inc(int i, int x) {
for (; i < N; i += i & -i) f[i] += x;
}
ll get(int i) {
ll res = 0;
for (; i >= 1; i -= i & -i) res += f[i];
return res;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) t[0][i] = a[i];
for (int h = 1; h < L; ++h) {
for (int i = 1; i + (1 << h) - 1 <= n; ++i) {
t[h][i] = max(t[h - 1][i], t[h - 1][i + (1 << (h - 1))]);
}
}
for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
for (int i = 1; i <= n; ++i) {
int t = 1;
while (true) {
int cur = get_max(max(1, i - t), i);
int l = t, r = n;
while (l <= r) {
int m = (l + r) / 2;
if (get_max(max(1, i - m), i) == cur) {
l = m + 1;
} else {
r = m - 1;
}
}
v.push_back({t, l - 1, i, cur});
if (l == n + 1) break;
t = l;
}
}
for (int i = 1; i <= q; ++i) {
int t, l, r; cin >> t >> l >> r;
qs[t].push_back({r, i});
qs[t].push_back({l - 1, -i});
}
for (auto [l, r, pos, val] : v) {
add[l].push_back({pos, val});
add[r + 1].push_back({pos, -val});
}
vector<ll> sol(q + 1);
for (int t = 1; t <= n; ++t) {
for (auto [pos, val] : add[t]) {
inc(pos, val);
}
for (auto [pos, i] : qs[t]) {
if (i > 0) sol[i] += get(pos);
if (i < 0) sol[-i] -= get(pos);
}
}
for (int i = 1; i <= q; ++i) cout << sol[i] << "\n";
}
