#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<vector<tuple<int, int, int>>> queries(n + 1);
    for (int i = 0; i < q; ++i) {
        int l, r, k;
        cin >> l >> r >> k;
        l--;
        queries[k].emplace_back(l, r, i);
    }

    vector<ll> ans(q);
    for (int k = 1; k <= n; ++k) {
        vector<int> mn(n - k + 1);
        deque<int> d;
        for (int i = 0; i < n; ++i) {
            while (!d.empty() && a[d.back()] >= a[i]) {
                d.pop_back();
            }
            d.push_back(i);
            if (i - k + 1 >= 0) {
                mn[i - k + 1] = a[d.front()];
                if (d.front() == i - k + 1) {
                    d.pop_front();
                }
            }
        }
        for (auto [l, r, i] : queries[k]) {
            for (int j = l; j + k <= r; ++j) {
                ans[i] += mn[j];
            }
        }
    }

    for (ll x : ans) {
        cout << x << '\n';
    }
}
