//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define mod 998244353
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct query{
int l, r, id;
query(){l = r = id = 0;}
query(int a, int b, int c){l = a, r = b, id = c;}
};
struct line{
ll m, k;
line(){m = k = 0;}
line(ll x, ll y){m = x, k = y;}
ll val(ll x){return m * x + k;}
line operator +(line l){
return line(m + l.m, k + l.k);
}
};
struct segtree{
line seg[4 * maxn];
void init(int cur, int l, int r, ll a[]) {
if (r <= l) return;
if (r - l == 1) {
seg[cur] = line{a[l], a[l]};
return;
}
int m = (l + r) / 2;
init(cur*2, l, m, a), init(cur*2+1, m, r, a);
seg[cur] = seg[cur*2] + seg[cur*2+1];
}
void modify(int cur, int l, int r, int ind, line li) {
if (r <= l) return;
if (r - l == 1) {
seg[cur] = li;
return;
}
int m = (l + r) / 2;
if (ind < m) modify(cur*2, l, m, ind, li);
else modify(cur*2+1, m, r, ind, li);
seg[cur] = seg[cur*2] + seg[cur*2+1];
}
ll query(int cur, int l, int r, int ql, int qr, int x) {
if (r <= l || ql >= r || qr <= l) return 0;
if (ql <= l && qr >= r) return seg[cur].val(x);
int m = (l + r) / 2;
return query(cur*2, l, m, ql, qr, x) + query(cur*2+1, m, r, ql, qr, x);
}
} tr;
struct sparse_table{
pii sp[18][maxn];
void build(int n, ll a[]) {
for (int i = 1;i <= n;i++) sp[0][i] = {a[i], i};
for (int i = 1;i < 18;i++) {
for (int j = 1;j <= n - (1<<i) + 1;j++) {
sp[i][j] = max(sp[i-1][j], sp[i-1][j + (1<<(i-1))]);
}
}
}
int query(int l, int r) { //[l, r]
l = max(l, 1);
int h = __lg(r - l + 1);
return max(sp[h][l], sp[h][r - (1<<h) + 1]).ss;
}
} sp;
vector<query> que[maxn];
vector<int> ev[maxn];
ll a[maxn], ans[maxn];
int lef[maxn], rig[maxn], type[maxn];
int main() {
io
int n, q;
cin >> n >> q;
for (int i = 1;i <= n;i++) cin >> a[i];
for (int i = 0;i < q;i++) {
int t, l, r;
cin >> t >> l >> r;
que[t].push_back(query(l, r, i));
}
stack<int> stk;
for (int i = 1;i <= n;i++) {
while (stk.size() && a[i] >= a[stk.top()]) {
rig[stk.top()] = i;
stk.pop();
}
if (stk.size()) lef[i] = stk.top();
else lef[i] = -n;
stk.push(i);
}
while (stk.size()) {
rig[stk.top()] = n + 1;
stk.pop();
}
for (int i = 1;i <= n;i++) {
if (i - lef[i] - 1 < maxn) ev[i - lef[i] - 1].push_back(i);
if (rig[i] - i - 1 < maxn) ev[rig[i] - i - 1].push_back(i);
if (rig[i] - lef[i] < maxn) ev[rig[i] - lef[i]].push_back(i);
}
tr.init(1, 1, n+1, a);
sp.build(n, a);
for (int i = 0;i <= n;i++) {
for (int j:ev[i]) {
//debug("ch", j);
if (type[j] < 2) {
ll cur = tr.query(1, 1, n+1, j, j+1, i);
tr.modify(1, 1, n+1, j, line(-type[j] * a[j], cur + type[j] * a[j] * i));
} else {
tr.modify(1, 1, n+1, j, line());
}
type[j]++;
}
for (auto [l, r, id]:que[i]) {
ans[id] = tr.query(1, 1, n+1, l - i, r+1, i);
debug(i, l, r);
int mr = sp.query(r-i, r), ml = sp.query(l - i, l);
debug(ans[id], ml, mr);
ans[id] -= (min(rig[mr] - 1, mr + i) - r) * a[mr];
ans[id] -= (l - max(lef[ml] + i + 1, ml)) * a[ml];
ans[id] -= tr.query(1, 1, n+1, l - i, ml, i);
ans[id] -= tr.query(1, 1, n+1, mr+1, r+1, i);
}
}
for (int i = 0;i < q;i++) cout << ans[i] << "\n";
}
/*
10 1
3 1 4 1 5 9 2 6 5 3
3 2 8
*/
