#include <bits/stdc++.h>

using LL = long long;

constexpr int inf32 = (int)(1e9) + 9;
constexpr LL inf64 = (LL)(1e18) + 18;
constexpr int N = 50004;

int n, q;
int a[N];

template <typename T>
using Vec = std::vector<T>;
Vec<LL> merge(Vec<LL> a, Vec<LL> b) {
    Vec<LL> _a(a.size() - 1), _b(b.size() - 1), _c(_a.size() + _b.size()), c(_c.size() + 1);
    for (int i = 0; i + 1 < a.size(); i++) _a[i] = a[i + 1] - a[i];
    for (int i = 0; i + 1 < b.size(); i++) _b[i] = b[i + 1] - b[i];
    std::merge(_a.begin(), _a.end(), _b.begin(), _b.end(), _c.begin(), std::greater<LL>());
    c[0] = a[0] + b[0];
    for (int i = 0; i < _c.size(); i++) c[i + 1] = c[i] + _c[i];
    return c;
}
Vec<LL> get_max(Vec<LL> a, Vec<LL> b) {
    if (a.size() > b.size()) std::swap(a, b);
    for (int i = 0; i < a.size(); i++) b[i] = std::max(a[i], b[i]);
    return b;
}
using Mat = std::array<std::array<Vec<LL>, 2>, 2>;
Mat merge(Mat x, Mat y) {
    Mat res = {};
    for (int a : {0, 1}) for (int b : {0, 1})
    for (int c : {0, 1}) for (int d : {0, 1}) {
        if (!x[a][b].size() || !y[c][d].size()) continue;
        auto cur = merge(x[a][b], y[c][d]);
        res[a][d] = get_max(res[a][d], cur);
        if (b && c) {
            cur.erase(cur.begin());
            res[a][d] = get_max(res[a][d], cur);
        }
    }
    return res;
}

constexpr int ls(int u) { return u << 1; }
constexpr int rs(int u) { return u << 1 | 1; }
Mat mat[N * 4];

void build(int u, int l, int r) {
    if (l == r) {
        mat[u][0][0] = {0};
        mat[u][1][1] = {-inf64, a[l]};
        return;
    }
    int mid = (l + r) / 2;
    build(ls(u), l, mid);
    build(rs(u), mid + 1, r);
    mat[u] = merge(mat[ls(u)], mat[rs(u)]);
}

struct Val {LL v; int c;};
Val operator+(Val a, Val b) {return {a.v + b.v, a.c + b.c};}
Val operator-(Val a, Val b) {return {a.v - b.v, a.c - b.c};}
bool operator<(Val a, Val b) {return a.v != b.v ? a.v < b.v : a.c < b.c;}

Val val[2];
void query(int u, int l, int r, int x, int y, int w) {
    if (x <= l && r <= y) {
        Val t[2] = {{-inf64, 0}, {-inf64, 0}};
        for (int a : {0, 1}) for (int b : {0, 1}) {
            auto &cur = mat[u][a][b];
            if (!cur.size()) continue;
            int le = 0, ri = cur.size() - 1;
            while (le < ri) {
                int mid = (le + ri) / 2;
                if (cur[mid + 1] - cur[mid] < -w) ri = mid;
                else le = mid + 1;
            }
            t[b] = std::max(t[b], std::max(val[0], val[1]) + Val{cur[le] + 1ll * w * le, le});
            if (a) t[b] = std::max(t[b], val[1] + Val{cur[le] + 1ll * w * (le - 1), le - 1});
        }
        val[0] = t[0];
        val[1] = t[1];
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid) query(ls(u), l, mid, x, y, w);
    if (y > mid) query(rs(u), mid + 1, r, x, y, w);
}
Val work(int l, int r, int w) {
    val[0] = {0, 0};
    val[1] = {-inf64, 0};
    query(1, 1, n, l, r, w);
    return std::max(val[0], val[1]);
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build(1, 1, n);
    for (int i = 1; i <= q; i++) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        int le = -inf32, ri = inf32;
        while (le < ri) {
            int mid = le + (ri - le) / 2;
            Val res = work(l, r, mid);
            if (res.c >= k) ri = mid;
            else le = mid + 1;
        }
        auto res = work(l, r, le);
        printf("%lld\n", res.v - 1ll * le * k);
    }
    std::cerr << 1. * std::clock() / CLOCKS_PER_SEC << std::endl;
    return 0;
}