#include <bits/stdc++.h>

using ll = long long;

using namespace std;

const int MAX_LOG = 17;
const int MAX_N = 1e5 + 10;

int table[MAX_LOG][MAX_N];

#define int ll

void calc(vector<int> a) {
    for (int i = 0; i < a.size(); i++) {
        table[0][i] = a[i];
    }
    for (int lg = 1; lg < MAX_LOG; lg++) {
        for (int i = 0; i < MAX_N; i++) {
            table[lg][i] = min(table[lg - 1][i], table[lg - 1][i + (1 << (lg - 1))]);
        }
    }
}

int get(int l, int r) {
    r++;
    int k = __lg(r - l);
    return min(table[k][l], table[k][r - (1 << k)]);
}

struct SegmentTree {
    vector<ll> t;
    int n = 1;
    SegmentTree(vector<int> a) {
        while (n < a.size()) {
            n *= 2;
        }
        t.resize(n * 2);
        build(0, 0, n - 1, a);
    }

    void build(int v, int tl, int tr, vector<int>& a) {
        if (tl == tr) {
            if (tl < a.size()) {
                t[v] = a[tl];
            }
            return;
        }
        int tm = (tl + tr) / 2;
        build(v * 2 + 1, tl, tm, a);
        build(v * 2 + 2, tm + 1, tr, a);
        t[v] = t[v * 2 + 1] + t[v * 2 + 2];
    }

    ll get(int ind) {
        ind += n - 1;
        return t[ind];
    }

    void change(int ind, int val) {
        ind += n - 1;
        t[ind] = val;
        while (ind != 0) {
            ind = (ind - 1) / 2;
            t[ind] = t[ind * 2 + 1] + t[ind * 2 + 2];
        }
    }

    ll get(int v, int tl, int tr, int ql, int qr) {
        if (qr < tl || tr < ql) {
            return 0;
        }
        if (ql <= tl && tr <= qr) {
            return t[v];
        }
        int tm = (tl + tr) / 2;
        return get(v * 2 + 1, tl, tm, ql, qr) + get(v * 2 + 2, tm + 1, tr, ql, qr);
    }

    ll get(int ql, int qr) { return get(0, 0, n - 1, ql, qr); }
};

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    // if (n == 100'000) {
    //     assert(0);
    // }
    vector<int> a(n);
    set<int> aboba;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        aboba.insert(a[i]);
    }

    vector<tuple<int, int, int>> qu(q);
    set<int> kek;
    set<pair<int, int>> clown;
    for (int i = 0; i < q; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        l--;
        r--;
        qu[i] = {l, r, k};
        kek.insert(k);
        clown.insert({l, r});
    }

    if (kek.size() == 1) {
        calc(a);

        int k = *kek.begin();
        vector<int> ans(n - k + 1);
        for (int i = 0; i + k - 1 < n; i++) {
            ans[i] = get(i, i + k - 1);
        }
        vector<ll> p(n - k + 2);
        for (int i = 0; i < ans.size(); i++) {
            p[i + 1] = p[i] + ans[i];
        }
        for (auto [l, r, k] : qu) {
            cout << p[r - k + 1 + 1] - p[l] << "\n";
        }
    } else if (*aboba.rbegin() <= 20) {
        vector<pair<int, pair<int, int>>> events;
        vector<int> z(21, -1);
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < a[i]; j++) {
                if (z[j] != -1) {
                    events.push_back({z[j] - i, {i, j}});
                }
            }
            z[a[i]] = i;
        }
        sort(events.rbegin(), events.rend());
        // reverse(events.begin(), events.end());

        vector<pair<tuple<int, int, int>, int>> quu(q);
        for (int i = 0; i < q; i++) {
            auto [l, r, k] = qu[i];
            quu[i] = {{k, l, r}, i};
        }
        sort(quu.begin(), quu.end());

        SegmentTree st(a);
        vector<int> ans(q);
        for (auto [o, ind] : quu) {
            auto [k, l, r] = o;
            while (events.size() && events.back().first < k) {
                auto [tm, w] = events.back();
                auto [i, j] = w;
                events.pop_back();

                if (a[i] > j) {
                    a[i] = j;
                    st.change(i, j);
                }
            }
            ans[ind] = st.get(l, r - k + 1);
        }
        // cout << "zzzz";
        for (auto x : ans) {
            cout << x << "\n";
        }

    } else if (clown.size() == 1 && *clown.begin() == pair<int, int>{0, n - 1}) {
        vector<int> nl(n), nr(n);
        vector<int> st;
        for (int i = 0; i < n; i++) {
            while (st.size() && a[st.back()] > a[i]) {
                nr[st.back()] = i;
                st.pop_back();
            }
        }
        while (st.size()) {
            nr[st.back()] = n;
            st.pop_back();
        }
        for (int i = n - 1; i >= 0; i--) {
            while (st.size() && a[st.back()] >= a[i]) {
                nl[st.back()] = i;
                st.pop_back();
            }
        }
        while (st.size()) {
            nl[st.back()] = -1;
            st.pop_back();
        }

        for (int i = 0; i < n; i++) {
            nl[i] = i - nl[i];
            nr[i] = nr[i] - i;
        }

        vector<tuple<int, int, int>> tr(n * 3);

        for (int i = 0; i < n; i++) {
            tr[i * 3] = {min(nl[i], nr[i]), 0, i};
            tr[i * 3 + 1] = {max(nl[i], nr[i]), 1, i};
            tr[i * 3 + 1] = {nl[i] + nr[i], 2, i};
        }

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

        int sum1 = accumulate(a.begin(), a.end(), int(0)), sum2 = 0, sum3 = 0;
        int cnt1 = n, cnt2 = 0;
        int dep = 0;
        multiset<int> g;
        vector<int> ans(n + 1);
        for (int k = 1; k <= n; k++) {
            ans[k] = sum1 + sum2 + sum3;
            while (tr.size() && get<0>(tr.back()) <= k) {
                auto [t, tp, i] = tr.back();
                tr.pop_back();
                if (tp == 0) {
                    cnt1--;
                    cnt2++;
                    sum1 -= (a[i] + k - 1);
                    sum2 += (a[i] + k - 1);
                } else if (tp == 1) {
                    cnt2--;
                    int el = a[i] + min(nl[i], nr[i]) - 1;
                    sum2 -= el;
                    sum3 += el;
                    g.insert(el + dep);
                }
            }
            sum1 += cnt1;
            while (g.size() && *g.begin() - dep == 1) {
                g.erase(g.begin());
            }
            dep += g.size();
            sum3 -= g.size();
        }

        for (auto [l, r, k] : qu) {
            cout << ans[k] << "\n";
        }


    } else {
        calc(a);
        for (auto [l, r, k] : qu) {
            ll ans = 0;
            for (int i = l; i + k - 1 <= r; i++) {
                ans += get(i, i + k - 1);
            }
            cout << ans << "\n";
        }
    }

    cout << "\n";
    return 0;
}
