#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
typedef pair<pll, pll> T;
pll operator+(pll p1, pll p2) { return pll(p1.first + p2.first, p1.second + p2.second); }
T operator+(T p1, T p2) { return T(p1.first + p2.first, p1.second + p2.second); }
pll operator-(pll p1, pll p2) { return pll(p1.first - p2.first, p1.second - p2.second); }
T operator-(T p1, T p2) { return T(p1.first - p2.first, p1.second - p2.second); }
struct fenwick {
vector<T> tree;
int N;
fenwick(int N) :N(N) {
tree.resize(N + 1);
}
void upd(int i, T x) {
while (i <= N) {
tree[i] = tree[i] + x;
i += i & -i;
}
}
T get(int i) {
T ans({ 0, 0 }, { 0, 0 });
while (i) {
ans = ans + tree[i];
i -= i & -i;
}
return ans;
}
};
vector<pair<int, pll>> del[MAX];
int arr[MAX];
int l[MAX];
int r[MAX];
int last[MAX];
vector<tuple<int, int, int>> qv[MAX];
T line[MAX];
ll ans[MAX];
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int N, Q;
cin >> N >> Q;
int i;
for (i = 1; i <= N; i++) cin >> arr[i];
vector<pii> stk = { { 1e9 + 10, 0 } };
for (i = 1; i <= N; i++) r[i] = N + 1;
for (i = 1; i <= N; i++) {
while (stk.back().first < arr[i]) {
r[stk.back().second] = i;
stk.pop_back();
}
l[i] = stk.back().second;
stk.emplace_back(arr[i], i);
}
for (i = 1; i <= N; i++) {
del[0].emplace_back(i, pll(1, arr[i]));
if (l[i]) {
del[i - l[i]].emplace_back(i, pll(-1, -arr[i]));
del[r[i] - l[i]].emplace_back(i, pll(1, arr[i]));
}
del[r[i] - i].emplace_back(i, pll(-1, -arr[i]));
}
int low, high, t;
for (i = 1; i <= Q; i++) {
cin >> t >> low >> high;
qv[t].emplace_back(low, high, i);
}
fenwick bit(N);
auto get = [&](int i, int t) {
if (i < 1) return 0ll;
int l, r;
l = 0;
r = N + 1;
while (r - l > 1) {
int mid = (l + r) / 2;
auto res = bit.get(mid);
if (t * res.first.first + res.first.second > i) r = mid;
else l = mid;
}
auto res = bit.get(l);
int ind = t * res.first.first + res.first.second;
return 1ll * arr[l + 1] * (i - res.first.first * t - res.first.second) + res.second.first * t + res.second.second;
};
for (i = 0; i <= N; i++) {
for (auto& [loc, p] : del[i]) {
T pv = line[loc];
auto& [a, b] = line[loc].first;
auto& [c, d] = line[loc].second;
a = line[loc].first.first;
b = line[loc].first.second;
ll y = a * i + b;
y += p.first;
a += p.first;
b = y - a * i;
c = line[loc].second.first;
d = line[loc].second.second;
y = c * i + d;
y += p.second;
c += p.second;
d = y - c * i;
bit.upd(loc, line[loc] - pv);
}
for (auto& [l, r, n] : qv[i]) ans[n] = get(r, i) - get(l - 1, i);
}
for (i = 1; i <= Q; i++) cout << ans[i] << ln;
}
