#include <bits/stdc++.h>
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 4e18;
const int OO = 1;
const int OOO = 1;
using namespace std;
struct fenwick {
int n;
vector<ll> t;
fenwick() {}
fenwick(int sz) {
n = sz;
t.resize(n + 1, 0);
}
void clear() {
for (auto &i : t) i = 0;
}
void add(int x, ll v) {
for (x++; x <= n; x += (x & -x)) t[x] += v;
}
ll query(int x) {
ll rtn = 0;
for (x++; x; x ^= (x & -x)) rtn += t[x];
return rtn;
}
ll query(int l, int r) {
return query(r) - query(l - 1);
}
};
struct query {
int l, r, i;
query() {}
query(int _l, int _r, int _i) {
l = _l;
r = _r;
i = _i;
}
};
struct eve {
int i;
ll v;
eve(int _i, ll _v) {
i = _i;
v = _v;
}
};
const int N = 2e5 + 5;
int n, q;
vector<int> s, L, R;
vector<query> que[N];
vector<ll> ans;
vector<eve> line[N], diag[N];
fenwick f;
void addline(int x, int y, int len, ll v) {
line[x].push_back(eve(y, v));
if (x + len <= n)
line[x + len].push_back(eve(y, -v));
}
void adddiag(int x, int y, int len, ll v) {
y = y - x + n;
diag[x].push_back(eve(y, v));
if (x + len <= n)
diag[x + len].push_back(eve(y, -v));
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> q;
s.resize(n), L.resize(n), R.resize(n);
ans.resize(q, 0);
f = fenwick(2 * n);
for (auto &i : s) cin >> i;
for (int i = 0, t, l, r; i < q; i++) {
cin >> t >> l >> r;
--l, --r;
que[t].push_back(query(l, r, i));
}
vector<pair<int, int>> st;
st.emplace_back(md, -md);
for (int i = 0; i < n; i++) {
while (st.back().first <= s[i]) st.pop_back();
L[i] = st.back().second;
st.emplace_back(s[i], i);
}
st.clear(), st.emplace_back(md, n);
for (int i = n - 1; i >= 0; i--) {
while (s[i] > st.back().first) st.pop_back();
R[i] = st.back().second;
st.emplace_back(s[i], i);
}
for (int i = 0; i < n; i++) {
if (i - L[i] < R[i] - i) {
// diagonal
for (int j = 0; j < i - L[i]; j++)
adddiag(j, i, R[i] - i, s[i]);
}
else {
// horizontal
for (int j = 0; j < R[i] - i; j++)
addline(j, i + j, i - L[i], s[i]);
}
}
// diagonal sweepline
for (int t = 0; t <= n; t++) {
for (const auto &i : diag[t])
f.add(i.i, i.v);
for (const auto &i : que[t])
ans[i.i] += f.query(i.l - t + n, i.r - t + n);
}
f.clear();
// horizontal sweepline
for (int t = 0; t <= n; t++) {
for (const auto &i : line[t])
f.add(i.i, i.v);
for (const auto &i : que[t])
ans[i.i] += f.query(i.l, i.r);
}
for (const auto &i : ans) cout << i << '\n';
}
