#include<bits/stdc++.h>
#define ll long long
#define sz(v) int(v.size())
using namespace std;
const int MAXN=35005;
const ll inf=1e12;
typedef vector<ll> poly;
poly operator *(poly f,poly g) {
	if(f.empty()||g.empty()) return {};
	poly h(sz(f)+sz(g)-1);
	int i=1,j=1,k=1; h[0]=f[0]+g[0];
	while(i<sz(f)&&j<sz(g)) {
		if(f[i]-f[i-1]>g[j]-g[j-1]) h[k]=h[k-1]+f[i]-f[i-1],++i,++k;
		else h[k]=h[k-1]+g[j]-g[j-1],++j,++k;
	}
	while(i<sz(f)) h[k]=h[k-1]+f[i]-f[i-1],++i,++k;
	while(j<sz(g)) h[k]=h[k-1]+g[j]-g[j-1],++j,++k;
	return h;
}
int n,q,a[MAXN];
poly tr[MAXN<<2][2][2];
void build(int l=1,int r=n,int p=1) {
	if(l==r) {
		tr[p][0][0]={0,a[l]},tr[p][0][1]=tr[p][1][0]=tr[p][1][1]={-inf,a[l]};
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,p<<1),build(mid+1,r,p<<1|1);
	for(int i:{0,1}) for(int j:{0,1}) {
		poly x=tr[p<<1][i][0]*tr[p<<1|1][0][j];
		poly y=tr[p<<1][i][1]*tr[p<<1|1][1][j];
		tr[p][i][j].resize(r-l+2);
		for(int k=0;k+1<sz(y);++k) tr[p][i][j][k]=max(x[k],y[k+1]);
		tr[p][i][j][r-l+1]=x[r-l+1];
	}
}
struct info {
	ll v; int c;
	friend info operator +(info x,info y) { return {x.v+y.v,x.c+y.c}; }
	friend bool operator <(info x,info y) { return x.v==y.v?x.c<y.c:x.v<y.v; }
};
typedef array<array<info,2>,2> mat;
info eval(poly &f,ll d) {
	int l=1,r=sz(f)-1,p=0;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(f[mid]-f[mid-1]>=d) l=mid+1,p=mid;
		else r=mid-1;
	}
	return {f[p]-d*p,p};
}
mat qry(int ul,int ur,ll d,int l=1,int r=n,int p=1) {
	if(ul<=l&&r<=ur) {
		mat f;
		for(int i:{0,1}) for(int j:{0,1}) f[i][j]=eval(tr[p][i][j],d);
		return f;
	}
	int mid=(l+r)>>1;
	if(ur<=mid) return qry(ul,ur,d,l,mid,p<<1);
	if(mid<ul) return qry(ul,ur,d,mid+1,p<<1|1);
	mat f=qry(ul,ur,d,l,mid,p<<1),g=qry(ul,ur,d,mid+1,p<<1|1),h;
	for(int i:{0,1}) for(int j:{0,1}) {
		h[i][j]=min(f[i][0]+g[0][j],f[i][1]+g[1][j]+info{d,-1});
	}
	return h;
}
signed main() {
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	build();
	for(int l,r,k;q--;) {
		scanf("%d%d%d",&l,&r,&k);
		ll L=-inf,R=inf,d=R;
		while(L<=R) {
			ll mid=(L+R)>>1;
			if(qry(l,r,mid)[0][0].c<=k) R=mid-1,d=mid;
			else L=mid+1;
		}
		printf("%lld\n",qry(l,r,d)[0][0].v+k*d);
	}
	return 0;
}