#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }
#define int ll
const int N = 2e5+7;
const int L = 20;
const int K = 450;
int n, a[N], q, lg[N];
vector<int> g[N];
pair<int, int> rmq[L][N];
vector<array<int, 3>> small[K];
int anc[L][N], mx[L][N], dep[N];
ll sum[L][N], b[N], pref[N], sol[N];
pair<int, int> join(pair<int, int> a, pair<int, int> b) {
if (a.first > b.first) {
return a;
} else if (a.first == b.first) {
return a.second < b.second ? a : b;
} else {
return b;
}
}
void dfs(int u) {
for (auto v : g[u]) {
dep[v] = dep[u] + 1;
anc[0][v] = u;
sum[0][v] = a[v] * (u - v);
mx[0][v] = u - v;
dfs(v);
}
}
int get_val_max(int l, int r) {
int p = lg[r - l + 1];
return max(rmq[p][l], rmq[p][r - (1 << p) + 1]).first;
}
int get_pos_max(int l, int r) {
int p = lg[r - l + 1];
return max(rmq[p][l], rmq[p][r - (1 << p) + 1]).second;
}
int get_first_bigger(int pos, int t) {
for (int h = L - 1; h >= 0; h--) {
if (mx[h][pos] <= t) {
pos = anc[h][pos];
}
}
return pos;
}
int lift(int x, int k) {
for (int h = L - 1; h >= 0; --h) {
if (k & (1 << h)) {
x = anc[h][x];
}
}
return x;
}
int get_before(int x, int y) {
if (x == y) return x;
return lift(x, dep[x] - dep[y] - 1);
}
ll get_sum(int a, int b) {
ll ans = 0;
for (int h = L - 1; h >= 0; --h) {
if (dep[a] - (1 << h) >= dep[b]) {
ans += sum[h][a];
a = anc[h][a];
}
}
return ans;
}
int get_until(int pos, int x) {
for (int h = L - 1; h >= 0; --h) {
if (anc[h][pos] <= x) {
pos = anc[h][pos];
}
}
return pos;
}
ll get(int t, int x) { // s(t)[1] + s(t)[2] + ... + s(t)[x]
int pos = 1;
ll ans = 0;
while (pos <= x) {
int last = get_first_bigger(pos, t);
// cout << "! " << pos << " " << last << "\n";
if (anc[0][last] <= x) {
ans += get_sum(pos, last);
if (last + t >= x) {
ans += a[last] * (x - last + 1);
break;
}
ans += a[last] * (t + 1);
pos = get_pos_max(last + 1, min(n, last + t + 1));
ans -= ((last + t) - pos + 1) * a[pos];
} else {
int stop = get_until(pos, x);
ans += get_sum(pos, stop);
ans += a[stop] * (x - stop + 1);
break;
}
}
return ans;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) rmq[0][i] = {a[i], i};
for (int h = 1; h < L; ++h) {
for (int i = 1; i + (1 << h) - 1 <= n; ++i) {
rmq[h][i] = join(rmq[h - 1][i], rmq[h - 1][i + (1 << (h - 1))]);
}
}
for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
vector<int> lft(n + 1), rgh(n + 1);
vector<int> stk;
for (int i = 1; i <= n; ++i) {
while (!stk.empty() && a[i] >= a[stk.back()]) stk.pop_back();
if (stk.empty()) lft[i] = -1e9;
if (!stk.empty()) lft[i] = stk.back() + 1;
stk.push_back(i);
}
stk.clear();
for (int i = n; i >= 1; --i) {
while (!stk.empty() && a[i] >= a[stk.back()]) stk.pop_back();
if (stk.empty()) rgh[i] = +1e9;
if (!stk.empty()) rgh[i] = stk.back();
stk.push_back(i);
}
for (int i = 1; i <= n; ++i) if (rgh[i] != 1e9) g[rgh[i]].push_back(i);
for (int i = 1; i <= n; ++i) if (rgh[i] == 1e9) mx[0][i] = 1e9, dfs(i);
for (int h = 1; h < L; ++h) {
for (int i = 1; i <= n; ++i) {
anc[h][i] = anc[h - 1][anc[h - 1][i]];
mx[h][i] = max(mx[h - 1][i], mx[h - 1][anc[h - 1][i]]);
sum[h][i] = sum[h - 1][i] + sum[h - 1][anc[h - 1][i]];
}
}
for (int i = 1; i <= q; ++i) {
int t, l, r; cin >> t >> l >> r;
// cout << "! " << get(t, r) - get(t, l - 1) << "\n";
if (t > K) {
sol[i] = get(t, r) - get(t, r - 1);
} else {
small[t].push_back({l, r, i});
}
}
for (int t = 1; t < K; ++t) {
for (int i = 1; i <= n; ++i) b[i] = get_val_max(max(1LL, i - t), i);
for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + b[i];
for (auto [l, r, i] : small[t]) sol[i] = pref[r] - pref[l - 1];
}
for (int i = 1; i <= q; ++i) cout << sol[i] << "\n";
}
