#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; }
const int N = 2e5+7;
const int L = 20;
int a[N], t[L][N], lg[N];
int get_max(int l, int r) {
int p = lg[r - l + 1];
return max(t[p][l], t[p][r - (1 << p) + 1]);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) t[0][i] = a[i];
for (int h = 1; h < L; ++h) {
for (int i = 1; i + (1 << h) - 1 <= n; ++i) {
t[h][i] = max(t[h - 1][i], t[h - 1][i + (1 << (h - 1))]);
}
}
for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
for (int i = 1; i <= q; ++i) {
int t, l, r; cin >> t >> l >> r;
ll ans = 0;
for (int j = l; j <= r; ++j) {
ans += get_max(max(1, j - t), j);
}
cout << ans << "\n";
}
}
