#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 2e5 + 5;
const int N = 4e5 + 5;
const int LG = 19;
int n, q;
int a[maxn];
long long res[maxn];
int le[maxn], ri[maxn];
vector<tuple<int, int, int>> ev[maxn];
vector<tuple<int, int, int>> que[maxn];
struct fenwick_tree {
long long bit[N];
void update(int i, long long val) {
for (; i < maxn; i += i & (-i)) {
bit[i] += val;
}
}
long long get(int i) {
long long ans = 0;
for (; i > 0; i -= i & (-i)) {
ans += bit[i];
}
return ans;
}
} fen[4];
void update(int l, int r, long long x) {
fen[0].update(l, x);
fen[1].update(r + 1, -x);
fen[2].update(l, -1ll * (l - 1) * x);
fen[3].update(r + 1, 1ll * r * x);
}
long long get(int i, int t) {
i += n;
// stable cases
long long res = fen[3].get(i) + fen[2].get(i - t);
// handling expansion cases
res += 1ll * (fen[1].get(i) + fen[0].get(i - t)) * (i - t);
return res + fen[1].get(i) * t;
}
void solve() {
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= q; ++i) {
int t, l, r; cin >> t >> l >> r;
que[t].emplace_back(l, r, i);
}
stack<int> st;
for (int i = 1; i <= n; ++i) {
while (!st.empty() and a[st.top()] <= a[i]) st.pop();
le[i] = (st.empty() ? -n : st.top());
st.push(i);
}
st = stack<int>();
for (int i = n; i; --i) {
while (!st.empty() and a[st.top()] < a[i]) st.pop();
ri[i] = (st.empty() ? n + 1 : st.top());
st.push(i);
auto add = [&](int l, int r, int x, int v) {
l += n, r += n;
ev[0].emplace_back(l, r, v);
if (x <= n) {
ev[x].emplace_back(l, r, -v);
}
};
if (le[i] + 1 < i) {
// expand
add(le[i] + 1, i - 1, i - le[i] - 1, -a[i]);
}
if (i + 1 < ri[i]) {
// expand
add(i + 1, ri[i] - 1, ri[i] - i - 1, -a[i]);
}
// decay
add(le[i] + 1, ri[i] - 1, ri[i] - le[i] - 1, a[i]);
}
for (int i = 0; i <= n; ++i) {
for (auto [l, r, x] : ev[i]) {
update(l, r, x);
}
for (auto [l, r, id] : que[i]) {
res[id] = get(r, i) - get(l - 1, i);
}
}
for (int i = 1; i <= q; ++i) {
cout << res[i] << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
