#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename T, class F = function<T(const T&, const T&)>>
class SegTree {
public:
T neutral = 0;
vector <T> t;
int sz;
F func;
SegTree() = default;
SegTree(int n, const F& f, T x = 0): func(f) {
init(n, x);
}
void init(int n, T x = 0) {
sz = n;
neutral = x;
t.assign(sz << 1, x);
}
void modify(int i, T v) {
int x = i + sz;
t[x] = v;
x >>= 1;
while (x) {
t[x] = func(t[x << 1], t[x << 1 | 1]);
x >>= 1;
}
}
T get(int l, int r) {
l += sz;
r += sz;
T ans = neutral;
while (l < r) {
if (l & 1) {
ans = func(ans, t[l++]);
}
if (r & 1) {
ans = func(ans, t[--r]);
}
l >>= 1;
r >>= 1;
}
return ans;
}
};
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];
}
SegTree<int> st(n, [](int i, int j) {return max(i, j);});
for (int i = 0; i < n; ++i) {
st.modify(i, s[i]);
}
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;
}
