#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
public:
int n;
vector<vector<T>> st;
F func;
SparseTable(const vector<T>& a, const F& f) : func(f) {
n = static_cast<int>(a.size());
int max_log = 32 - __builtin_clz(n);
st.resize(max_log);
st[0] = a;
for (int j = 1; j < max_log; ++j) {
st[j].resize(n - (1 << j) + 1);
for (int i = 0; i <= n - (1 << j); ++i) {
st[j][i] = func(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
}
}
SparseTable() = default;
T get(int L, int R) const {
assert(0 <= L && L < R && R <= n);
int lg = __lg(R - L);
return func(st[lg][L], st[lg][R - (1 << lg)]);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
SparseTable<int> st(s, [](int i, int j) {return max(i, j);});
while (q--) {
int t, l, r;
cin >> t >> l >> r;
ll ans = 0;
for (int i = l - 1; i < r; ++i) {
ans += st.get(max(0, i - t), i + 1);
}
cout << ans << '\n';
}
return 0;
}
