rt，复杂度 $O(n \log ^2 n)$，思路是二分分界点（分界点左边的人往右走， 分界点右边的人往左走）。

TLE $70$ pts。

#include <bits/stdc++.h>
#define _for(i, a, b)  for (int i = (a); i <= (b); i ++ )
#define ll long long
#define P pair<int, ll>
#define F first
#define S second
#define mp make_pair
using namespace std;
const int N = 5e5 + 5;
int n, m, q, a[N], b[N], rt[N]; ll s[N];
namespace IO {
	static char buf[1000000], * p1 = buf, * p2 = buf, obuf[1000000], * p3 = obuf, cc[20];
	#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, N - 5, stdin), p1 == p2) ? EOF : * p1 ++ )
	#define pc(x) (p3 - obuf < 1000000) ? ( * p3 ++ = x) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, * p3 ++ = x)
	inline int rd() {
		int val = 0, sgn = 1; char ch = gc();
		while (! isdigit(ch)) { if (ch == '-')  sgn = -1; ch = gc(); }
		while (isdigit(ch))  val = (val << 3) + (val << 1) + (ch ^ 48), ch = gc();
		return (val * sgn);
	}
	template <typename item>
	inline void print(item x){ 
		if (! x)  pc('0');
		int len = 0;
		if (x < 0)  x = - x, pc('-');
		while (x)  cc[len ++ ] = x % 10 | '0', x /= 10;
		while (len -- )  pc(cc[len]);
	}
	inline void write(ll x, char c) { print(x), pc(c); }
} using namespace IO;
struct HJT_Seg_Tree {
	#define lc(u)  tr[u].ls
	#define rc(u)  tr[u].rs
	#define val(u)  tr[u].val
	#define sum(u)  tr[u].sum
	#define mid ((tr[p].l + tr[p].r) >> 1)
	int cnt = 0;
	struct Node { int l, r, ls, rs, val; ll sum; } tr[N << 5];
	inline int len(int p) { return tr[p].r - tr[p].l + 1; }
	inline int clone(int p, int x) { tr[ ++ cnt] = tr[p], val(cnt) ++ , sum(cnt) += b[x]; return cnt; }
	int build(int p, int l, int r) {
		tr[p = ++ cnt] = (Node){l, r, 0, 0, 0, 0};
		if (l == r)  return p;
		lc(p) = build(lc(p), l, mid), rc(p) = build(rc(p), mid + 1, r); return p;
	}
	int update(int p, int x) {
		p = clone(p, x);
		if (len(p) == 1)  return p;
		if (x <= mid)  return lc(p) = update(lc(p), x), p;
		return rc(p) = update(rc(p), x), p;
	}
	P query(int u, int v, int k) {
		if (len(u) == 1)  return mp(tr[u].l, val(v) == val(u) ? 0 : (sum(v) - sum(u)) / (val(v) - val(u)) * k);
		int val = val(lc(v)) - val(lc(u));
		if (k <= val)  return query(lc(u), lc(v), k);
		P res = query(rc(u), rc(v), k - val);
		return mp(res.F, res.S + sum(lc(v)) - sum(lc(u)));
	}
	#undef lc(u)
	#undef rc(u)
	#undef val(u)
	#undef sum(u)
	#undef mid
} T;
inline ll calc(int st, int len) { return len >= 0 ? 1ll * (2 * st + len - 1) * len / 2 : 0; }
int main() {
	ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
	n = rd(), q = rd(); int l, r, k, L, R, mid, pos; ll tmp;
	_for (i, 1, n)  a[i] = rd(), b[i] = a[i], s[i] = s[i - 1] + a[i];
	sort(b + 1, b + n + 1), m = unique(b + 1, b + n + 1) - b - 1, rt[0] = T.build(rt[0], 1, m);
	_for (i, 1, n)  a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b, rt[i] = T.update(rt[i - 1], a[i]);
	while (q -- ) {
		l = rd(), r = rd(), k = rd(), L = 0, R = r - l + 1, pos = 0;
		while (L <= R) {
			mid = (L + R) >> 1;
			if (b[T.query(rt[l - 1], rt[r], mid).F] <= k + mid - 1)  pos = mid, L = mid + 1;
			else  R = mid - 1;
		}
		tmp = T.query(rt[l - 1], rt[r], pos).S, write(calc(k, pos) - tmp + s[r] - s[l - 1] - tmp - calc(k + pos, r - l + 1 - pos), '\n');
	}
	fwrite(obuf, p3 - obuf, 1, stdout);
	return 0;
}