#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif // LOCAL
#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>
const int N = 2e5 + 5;
const ll inf = 1e18;
struct BIT {
int n;
ll bit[2 * N + 1];
BIT() {}
BIT(int n) : n(n) {}
void update(int id, ll val) {
id += N;
for (int i = id; i <= n; i += (i & -i)) bit[i] += val;
}
ll get(int id) {
ll res = 0;
id += N;
for (int i = id; i > 0; i -= (i & -i)) res += bit[i];
return res;
}
} bit1(2 * N), bit2(2 * N), bit3(2 * N), bit4(2 * N), bit5(2 * N);
struct Query {
int l, r, id;
};
vector<Query> que[N];
vector<pair<int, ll>> ev1[2 * N], ev2[2 * N], ev3[2 * N], ev4[2 * N], ev5[2 * N];
int n, q;
ll res[N];
int a[N], l[N], r[N];
vector<int> vec;
ll cal(int t, int r) {
return 1ll * (r - t) * (bit1.get(r - t) + bit2.get(r)) + (bit3.get(r - t) + bit4.get(r)) + 1ll * t * bit5.get(r);
}
void add_tri(int l, int r, int val) {
ev1[0].pb({l, val});
ev2[0].pb({r + 1, - val});
ev3[0].pb({l, -1ll * val * (l - 1)});
ev4[0].pb({r + 1, 1ll * val * r});
ev5[0].pb({r + 1, - val});
ev1[r - l + 1].pb({l, - val});
ev2[r - l + 1].pb({r + 1, val});
ev3[r - l + 1].pb({l, 1ll * val * (l - 1)});
ev4[r - l + 1].pb({r + 1, - 1ll * val * r});
ev5[r - l + 1].pb({r + 1, val});
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= q; i++) {
int t, u, v;
cin >> t >> u >> v;
que[t].pb({u, v, i});
}
for (int i = 1; i <= n; i++) {
while(!vec.empty() && a[i] >= a[vec.back()]) vec.pop_back();
if (vec.empty()) l[i] = - n - 2;
else l[i] = vec.back();
vec.pb(i);
}
vec.clear();
for (int i = n; i >= 1; i--) {
while(!vec.empty() && a[i] > a[vec.back()]) vec.pop_back();
if (vec.empty()) r[i] = n + 2;
else r[i] = vec.back();
vec.pb(i);
}
for (int i = 1; i <= n; i++) {
add_tri(l[i] + 1, r[i] - 1, a[i]);
add_tri(l[i] + 1, i - 1, - a[i]);
add_tri(i + 1, r[i] - 1, - a[i]);
}
for (int i = 0; i <= n; i++) {
for (auto it : ev1[i]) bit1.update(it.F, it.S);
for (auto it : ev2[i]) bit2.update(it.F, it.S);
for (auto it : ev3[i]) bit3.update(it.F, it.S);
for (auto it : ev4[i]) bit4.update(it.F, it.S);
for (auto it : ev5[i]) bit5.update(it.F, it.S);
for (auto it : que[i]) {
res[it.id] = cal(i, it.r) - cal(i, it.l - 1);
}
}
for (int i = 1; i <= q; i++) {
cout << res[i] << '\n';
}
}
