#include <algorithm>
#include <cassert>
#include <chrono>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <random>
#include <set>
#include <vector>
#include <cmath>

using namespace std;
#define ll long long

struct dsu {
    vector <int> par;
    vector <int> mn;
    vector <int> sz;

    dsu(vector <int> a) : mn(a) {
        int n = a.size();
        par.resize(n);
        sz.resize(n, 1);
        for (int i = 0; i < n; ++i) {
            par[i] = i;
        }
    }

    int parent(int v) {
        if (v == par[v]) return v;
        return par[v] = parent(par[v]);
    }

    bool unite(int a, int b) {
        a = parent(a);
        b = parent(b);
        if (a == b) return false;
        sz[b] += sz[a];
        par[a] = b;
        mn[b] = min(mn[b], mn[a]);
        return true;
    }
};

struct Fenwick {
    int n;
    vector <ll> f;

    Fenwick(int n) : n(n) {
        f.resize(n + 1);
    }

    Fenwick() {}

    inline void add(int i, ll x) {
        for (++i; i <= n; i += (i & (-i))) f[i] += x;
    }

    inline ll get_pref(int i) {
        ll ans = 0;
        for (++i; i > 0; i -= (i & (-i))) ans += f[i];
        return ans;
    }

    inline ll get_seg(int l, int r) {
        return get_pref(r) - get_pref(l - 1);
    }
};

struct SegTree {
    int n;
    vector <vector <int>> poses;
    vector <Fenwick> f1, f2;

    SegTree(int n) : n(n) {
        poses.resize(4 * n);
        f1.resize(4 * n);
        f2.resize(4 * n);
    }

    void add_point(int v, int l, int r, int i, int x) {
        if (l > i || i > r) return;
        poses[v].push_back(x);
        if (l == r) return;
        int m = (l + r) / 2;
        add_point(2 * v, l, m, i, x);
        add_point(2 * v + 1, m + 1, r, i, x);
    }

    void build(int v, int l, int r) {
        sort(poses[v].begin(), poses[v].end());
        poses[v].resize(unique(poses[v].begin(), poses[v].end()) - poses[v].begin());
        int ln = poses[v].size();
        f1[v] = Fenwick(ln);
        f2[v] = Fenwick(ln);
        if (l == r) return;
        int m = (l + r) / 2;
        build(2 * v, l, m);
        build(2 * v + 1, m + 1, r);
    }

    void add_val(int v, int l, int r, int i, int x, int coef) {
        if (l > i || i > r) return;
        int pos = lower_bound(poses[v].begin(), poses[v].end(), x) - poses[v].begin();

        f1[v].add(pos, 1ll * coef * x);
        f2[v].add(pos, coef);
        if (l == r) return;
        int m = (l + r) / 2;
        add_val(2 * v, l, m, i, x, coef);
        add_val(2 * v + 1, m + 1, r, i, x, coef);
    }

    ll get_res(int v, int l, int r, int A, int B, int k) {
        if (l > B || A > r) return 0;
        if (A <= l && r <= B) {
            int f_ok = lower_bound(poses[v].begin(), poses[v].end(), k) - poses[v].begin();
            if (f_ok == poses[v].size()) return 0;

            return f1[v].get_seg(f_ok, poses[v].size() - 1) - f2[v].get_seg(f_ok, poses[v].size() - 1) * (k - 1);
        }
        int m = (l + r) / 2;
        return get_res(2 * v, l, m, A, B, k) + get_res(2 * v + 1, m + 1, r, A, B, k);
    }
};

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

    vector <array <int, 3>> segs;
    dsu flex(a);
    vector <int> on(n);

    auto merge = [&](int old, int added) {
        if (!on[old]) return;

        int val = flex.mn[flex.parent(old)];
        if (a[added] < val) {
            if (old + 1 == added) {
                segs.push_back({old - flex.sz[flex.parent(old)] + 1, old, val - a[added]});
            } else {
                segs.push_back({old, old + flex.sz[flex.parent(old)] - 1, val - a[added]});
            }
        }

        flex.unite(old, added);
    };

    vector <pair <int, int>> ord;
    for (int i = 0; i < n; ++i) {
        ord.emplace_back(a[i], i);
    }
    sort(ord.rbegin(), ord.rend());
    for (auto i : ord) {
        if (i.second > 0) merge(i.second - 1, i.second);
        if (i.second + 1 < n) merge(i.second + 1, i.second);

        on[i.second] = 1;
    }

    segs.push_back({0, n - 1, *min_element(a.begin(), a.end())});

    vector <array <int, 3>> all_q(q);
    for (int i = 0; i < q; ++i) {
        cin >> all_q[i][0] >> all_q[i][1] >> all_q[i][2]; --all_q[i][0]; --all_q[i][1];
    }

    vector <ll> answer(q);

    vector <array <int, 3>> events1;

    for (int i = 0; i < q; ++i) {
        events1.push_back({all_q[i][1], -(i + 1), 0});
    }
    for (auto [l, r, coef] : segs) {
        events1.push_back({r, (l + 1), coef});
    }

    sort(events1.rbegin(), events1.rend());
    Fenwick f(n);
    
    for (auto ev : events1) {
        if (ev[1] < 0) {
            int index = -ev[1] - 1;

            answer[index] += f.get_pref(all_q[index][0]) * (all_q[index][1] - all_q[index][0] + 1 - all_q[index][2] + 1);
        } else {
            int real_l = ev[1] - 1;
            f.add(real_l, ev[2]);
        }
    }

    f = Fenwick(n);
    Fenwick f2(n);

    for (auto& i : events1) {
        i[1] *= -1;
    }

    sort(events1.rbegin(), events1.rend());

    for (auto ev : events1) {
        if (ev[1] > 0) {
            int index = ev[1] - 1;
            int l = all_q[index][0];
            int r = all_q[index][1];
            int k = all_q[index][2];
            r = r - k + 1;
            if (l + 1 > r) continue;

            ll part_minus = f2.get_seg(l + 1, r);
            ll part_plus = f.get_seg(l + 1, r);
            answer[index] += part_plus * (all_q[index][1] - k + 2) - part_minus;
        } else {
            int real_l = -ev[1] - 1;

            f.add(real_l, ev[2]);
            f2.add(real_l, 1ll * ev[2] * real_l);
        }
    }

    events1.clear();
    f = Fenwick(n);
    f2 = Fenwick(n);

    for (int i = 0; i < q; ++i) {
        events1.push_back({all_q[i][0], -(i + 1), 0});
    }
    for (auto [l, r, coef] : segs) {
        events1.push_back({l, (r + 1), coef});
    }

    sort(events1.begin(), events1.end());

    for (auto ev : events1) {
        if (ev[1] < 0) {
            int index = -ev[1] - 1;
            int l = all_q[index][0];
            int r = all_q[index][1];
            int k = all_q[index][2];
            l = l + k - 1;
            if (l > r - 1) continue;

            ll part_minus = f2.get_seg(l, r - 1);
            ll part_plus = f.get_seg(l, r - 1);
            answer[index] += part_plus * (-all_q[index][0] - k + 2) + part_minus;
        } else {
            int real_r = ev[1] - 1;

            f.add(real_r, ev[2]);
            f2.add(real_r, 1ll * ev[2] * real_r);
        }
    }

    SegTree t(n);

    for (auto i : segs) {
        t.add_point(1, 0, n - 1, i[1], i[1] - i[0] + 1);
    }

    t.build(1, 0, n - 1);

    events1.clear();
    for (int i = 0; i < q; ++i) {
        events1.push_back({all_q[i][0], -(i + 1), 0});
    }
    for (auto [ql, qr, coef] : segs) {
        events1.push_back({ql, qr + 1, coef});
    }

    sort(events1.rbegin(), events1.rend());

    for (auto ev : events1) {
        if (ev[1] < 0) {
            int index = -ev[1] - 1;
            int l = all_q[index][0];
            int r = all_q[index][1];
            int k = all_q[index][2];
            answer[index] += t.get_res(1, 0, n - 1, l, r, k);
        } else {
            int real_r = ev[1] - 1;

            t.add_val(1, 0, n - 1, real_r, real_r - ev[0] + 1, ev[2]);
        }
    }

    map <pair <int, int>, int> map_seg;
    for (auto [ql, qr, coef] : segs) {
        map_seg[make_pair(ql, qr)] = coef;
    }

    for (int i = 0; i < q; ++i) {
        int l = all_q[i][0];
        int r = all_q[i][1];
        int k = all_q[i][2];
        if (map_seg.count(make_pair(l, r))) {
            answer[i] -= 1ll * map_seg[make_pair(l, r)] * (r - l + 1 - k + 1);
        }

        // for (auto [ql, qr, coef] : segs) {
        //     if (ql <= l && qr >= r) continue;
        //     if (qr > r && ql > l) continue;
        //     if (ql < l && qr < r) continue;
        //     ql = max(ql, l);
        //     qr = min(qr, r);
        //     int len = qr - ql + 1;
        //     if (len >= k) answer[i] += 1ll * coef * (len - k + 1);
        // }

        cout << answer[i] << "\n";
    }
}

signed main() {
    if (1) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
    }
    if (1) {
        int t = 1;
        // cin >> t;
        while (t--) {
            solve();
        }
    }
}

/*
4 4
2 2
2 3

*/
