#include <bits/stdc++.h>
#define ls num << 1
#define rs ls | 1
#define li ls, l, mid
#define ri rs, mid + 1, r
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	x *= f;
}
const int N = 5e4 + 10;
int num, n, q, a[N];
struct point {
    int x; ll y;
    friend point operator + (const point &a, const point &b) {
        return {a.x + b.x, a.y + b.y};
    }
    friend point operator - (const point &a, const point &b) {
        return {a.x - b.x, a.y - b.y};
    }
    friend ll operator * (const point &a, const point &b) {
        return a.x * b.y - a.y * b.x;
    }
    friend bool operator > (const point &a, const point &b) {
        return a * b <= 0;
    }
};
int K;
struct hull {
    vector <point> x;
    int pos;
    hull () {
        pos = 0;
    }
    friend hull operator + (const hull &x, const hull &y) {
        hull ans; ans.x.resize(x.x.size() + y.x.size() - 1);
        ans.x[0]= x.x[0] + y.x[0];
        unsigned l = 0, r = 0;
        while (l < SZ(x.x) && r < SZ(y.x)) {
            point A = x.x[l + 1] - x.x[l], B = y.x[r + 1] - y.x[r];
            if (A > B) ans.x[l + r + 1] = ans.x[l + r] + A, l++;
            else ans.x[l + r + 1] = ans.x[l + r] + B, r++;
        }
        while (l < SZ(x.x)) ans.x[l + r + 1] = ans.x[l + r] + x.x[l + 1] - x.x[l], l++;
        while (r < SZ(y.x)) ans.x[l + r + 1] = ans.x[l + r] + y.x[r + 1] - y.x[r], r++;
        return ans;
    }
    friend hull operator + (hull x, const point &y) {
        for (point &i: x.x) i = i + y;
        return x;
    }
    friend hull operator * (const hull &x, const hull &y) {
        hull ans; ans.x.resize(x.x.size() + y.x.size());
        unsigned l = 0, r = 0; int sz = -1;
        while (l < x.x.size() || r < y.x.size()) {
            point tmp;
            if (r != y.x.size() && (l == x.x.size() || (x.x[l].x > y.x[r].x || (x.x[l].x == y.x[r].x && x.x[l].y > y.x[r].y)))) tmp = y.x[r], r++;
            else tmp = x.x[l], l++;
            while (sz >= 1 && tmp - ans.x[sz] > ans.x[sz] - ans.x[sz - 1]) sz--;
            ans.x[++sz] = tmp;
        }
        ans.x.resize(sz + 1);
        return ans;
    }
    ll qq(const point &x) {
        return (ll) x.x * K + x.y;
    }
    point qry() {
		// cout << "# " << pos << endl;
        while (pos < SZ(x) && qq(x[pos]) < qq(x[pos + 1])) pos++;
        return {x[pos].x, qq(x[pos])};
    }
};
struct ment {
    hull lans, rans, lrans, ans;
    friend ment operator + (const ment &x, const ment &y) {
        return {(x.lans + y.ans) * (x.lrans + y.lans + (point) {-1, 0}),
        (y.rans + x.ans) * (y.lrans + x.rans + (point) {-1, 0}),
        (x.lans + y.rans) * (x.lrans + y.lrans + (point) {-1, 0}),
		(x.ans + y.ans) * (x.rans + y.lans + (point) {-1, 0})};
    }
} seg[N << 2];
void build(int num, int l, int r) {
	if (l == r) {
		seg[num].lans.x = seg[num].rans.x = seg[num].lrans.x = vector{(point) {1, a[l]}};
		seg[num].ans.x = vector{(point) {0, 0}, (point) {1, a[l]}};
		return;
	}
	int mid = (l + r) >> 1;
	build(li), build(ri);
	seg[num] = seg[ls] + seg[rs];
	// for (point i: seg[ls].rans.x) cout << num << " " << l << " " << r << " -> " << i.x << " " << i.y << endl;
	// for (point i: seg[rs].lans.x) cout << num << " " << l << " " << r << " -> " << i.x << " " << i.y << endl;
}
struct QQ {
	int l, r, k, id;
	int tl, tr, mid;
} Q[N];
point Max(point x, point y) {
	if (x.y != y.y)
	return x.y > y.y ? x : y;
	return x.x < y.x ? x : y;
}
struct P {
	point lans, rans, lrans, ans;
	friend P operator + (P x, P y) {
		return {Max(x.lans + y.ans, x.lrans + y.lans + (point) {-1, -K}), Max(y.rans + x.ans, y.lrans + x.rans + (point) {-1, -K}), Max(x.lans + y.rans, x.lrans + y.lrans + (point) {-1, -K}), Max(x.ans + y.ans, x.rans + y.lans + (point) {-1, -K})};
	}
};
P query(int num, int l, int r, int L, int R) {
	if (L <= l && r <= R) {
		// P x = 
		return {seg[num].lans.qry(), seg[num].rans.qry(), seg[num].lrans.qry(), seg[num].ans.qry()};
		// cout << num << " " << l << " " << r << " " << x.ans.x << " % " << x.ans.y << endl;
		// return x;
	}
	int mid = (l + r) >> 1;
	if (mid >= R) return query(li, L, R);
	if (mid < L) return query(ri, L, R);
	return query(li, L, R) + query(ri, L, R);
}
ll ans[N];
signed main() {
	read(n), read(q);
	F(i, 1, n) read(a[i]);
	build(1, 1, n);
	// for (point x: seg[1].ans.x) cout << "! " << x.x << " " << x.y << endl;
	// return 0;
	F(i, 1, q) read(Q[i].l), read(Q[i].r), read(Q[i].k), Q[i].tl = -1e9, Q[i].tr = 1e9, Q[i].id = i;
	while (true) {
		bool flag = true;
		F(i, 1, q) Q[i].mid = (Q[i].tl + Q[i].tr) >> 1;
		F(i, 1, n * 4) seg[i].ans.pos = seg[i].lans.pos = seg[i].rans.pos = seg[i].lrans.pos = 0;
		sort(Q + 1, Q + q + 1, [&] (QQ x, QQ y) {
			return x.mid < y.mid;
		});
		F(i, 1, q) {
			if (Q[i].tl + 1 < Q[i].tr) {
				flag = false;
				K = Q[i].mid;
				P t = query(1, 1, n, Q[i].l, Q[i].r);
				// cout << "# " << K << " " << t.ans.x << " " << t.ans.y << endl;
				if (t.ans.x <= Q[i].k) Q[i].tl = K, ans[Q[i].id] = t.ans.y - (ll) K * Q[i].k;
				else Q[i].tr = K;
			}
		}
		if (flag) break;
	}
	F(i, 1, q) cout << ans[i] << '\n';
	return 0;
}
// inaugurate