#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct FenwickTree {
    int n;
    vector<int> t;

    explicit FenwickTree(int size) : n(size), t(size + 1) {}

    int get(int r) {
        int res = 0;
        for (; r > 0; r -= r & -r) {
            res += t[r];
        }
        return res;
    }

    int get(int l, int r) {
        return get(r) - get(l);
    }

    void update(int i, int x) {
        i += 1;
        for (; i <= n; i += i & -i) {
            t[i] += x;
        }
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<int> b = a;
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());

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

    for (int j = 1; j < b.size(); ++j) {
        int next_zero = n;
        vector<vector<int>> updates(n + 2);
        for (int i = n - 1; i >= 0; --i) {
            if (a[i] < b[j]) {
                next_zero = i;
            }
            updates[next_zero - i + 1].push_back(i);
        }
        FenwickTree ft(n);
        for (int k = 1; k <= n; ++k) {
            for (int i : updates[k]) {
                ft.update(i, -1);
            }
            for (auto [l, r, i] : queries[k]) {
                ans[i] += (ll)(b[j] - b[j - 1]) * ft.get(l, r - k + 1);
            }
        }
    }

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