#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <typename T>
struct SparseTable { //max
int n;
vector<vector<T>> st;
SparseTable(const vector<T>& a) {
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] = max(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 max(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);
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;
}
