#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct Linear {
    ll k, b;

    Linear() : k(0), b(0) {}
    Linear(ll k, ll b) : k(k), b(b) {}

    ll operator()(ll x) const {
        return k * x + b;
    }

    Linear operator+(Linear f) const {
        return {k + f.k, b + f.b};
    }
};

struct LinearSegmentTree {
    int n;
    vector<Linear> t;

    explicit LinearSegmentTree(int size) : n(size), t(2 * size) {}

    Linear get(int l, int r) const {
        Linear res;
        l += n;
        r += n;
        while (l < r) {
            if (l & 1) {
                res = res + t[l++];
            }
            if (r & 1) {
                res = res + t[--r];
            }
            l /= 2;
            r /= 2;
        }
        return res;
    }

    void update(int i, Linear f) {
        i += n;
        t[i] = f;
        i /= 2;
        while (i > 0) {
            t[i] = t[i * 2] + t[i * 2 + 1];
            i /= 2;
        }
    }
};

const int INF = 1e9;

struct MinSegmentTree {
    int n;
    vector<pair<int, int>> t;

    explicit MinSegmentTree(const vector<int>& a) : n(a.size()), t(2 * a.size()) {
        for (int i = 0; i < n; ++i) {
            t[i + n] = {a[i], i};
        }
        for (int i = n - 1; i > 0; --i) {
            t[i] = min(t[i * 2], t[i * 2 + 1]);
        }
    }

    int get(int l, int r) const {
        pair<int, int> res = {INF, -1};
        l += n;
        r += n;
        while (l < r) {
            if (l & 1) {
                res = min(res, t[l++]);
            }
            if (r & 1) {
                res = min(res, t[--r]);
            }
            l /= 2;
            r /= 2;
        }
        return res.second;
    }
};

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<int> l_min(n, -1), r_min(n, n);
    {
        vector<int> st;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && a[st.back()] > a[i]) {
                r_min[st.back()] = i;
                st.pop_back();
            }
            if (!st.empty()) {
                l_min[i] = st.back();
            }
            st.push_back(i);
        }
    }

    vector<vector<pair<int, Linear>>> events(n + 2);
    for (int i = 0; i < n; ++i) {
        int l = l_min[i], r = r_min[i];
        events[0]
            .emplace_back(i, Linear(a[i], 0));
        events[min(i - l, r - i)]
            .emplace_back(i, Linear(0, (ll)a[i] * min(i - l, r - i)));
        events[max(i - l, r - i)]
            .emplace_back(i, Linear(-a[i], (ll)a[i] * (r - l)));
        events[r - l]
            .emplace_back(i, Linear(0, 0));
    }

    LinearSegmentTree linear_st(n);
    MinSegmentTree min_st(a);
    vector<ll> ans(q);
    for (int k = 0; k <= n; ++k) {
        for (auto [i, new_f] : events[k]) {
            linear_st.update(i, new_f);
        }
        for (auto [l, r, i] : queries[k]) {
            int first = min_st.get(l, l + k);
            int last = min_st.get(r - k, r);
            if (first == last) {
                ans[i] += (ll)a[first] * (r - l - k + 1);
            } else {
                ans[i] += (ll)a[first] * min(first - l + 1, r_min[first] - l - k + 1);
                ans[i] += (ll)a[last] * min(r - last, r - l_min[last] - k);
                ans[i] += linear_st.get(first + 1, last)(k);
            }
        }
    }

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