#include<bits/stdc++.h>
#define MN -2000000000
using namespace std;
int n,q,a[50005];
const long long ZZ=1e10;
struct tubao{
	vector<int>vc;
	vector<int>cv;
}sm[131073][2][2];
long long aa[50005],bb[50005],cc[50005],cz[50005];
tubao hebing(tubao a,tubao b){
	int s1=a.vc.size(),s2=b.vc.size();
	for(int i=1;i<s1;++i)aa[i]=0ll+a.vc[i-1]-a.vc[i];
	for(int i=1;i<s2;++i)bb[i]=0ll+b.vc[i-1]-b.vc[i];
	merge(aa+1,aa+s1,bb+1,bb+s2,cc+1);
	cz[0]=0ll+a.vc[0]+b.vc[0];
	for(int i=1;i<=s1+s2-2;++i)cz[i]=cz[i-1]-cc[i];
	tubao c;
	c.vc.resize(s1+s2-1);
	for(int i=0;i<s1+s2-1;++i)c.vc[i]=max(0ll+MN,cz[i]);
	return c;
}
tubao mini(tubao a,tubao b){
	tubao c;c.vc.resize(max(a.vc.size(),b.vc.size()));
	for(int i=0;i<(signed)c.vc.size();++i)c.vc[i]=MN;
	for(int i=0;i<(signed)a.vc.size();++i)
		c.vc[i]=max(c.vc[i],a.vc[i]);
	for(int i=0;i<(signed)b.vc.size();++i)
		c.vc[i]=max(c.vc[i],b.vc[i]);
	return c;
}
void tudd(int o){
	for(int i=0;i<2;++i)for(int j=0;j<2;++j){
		int sz=sm[o][i][j].vc.size();
		for(int k=sz-2;k>=(i==0&&j==1);--k)
			sm[o][i][j].cv.emplace_back(sm[o][i][j].vc[k+1]-sm[o][i][j].vc[k]);
	}
}
void build(int l,int r,int o){
	if(l==r){
		for(int i=0;i<2;++i)for(int j=0;j<2;++j){
			sm[o][i][j].vc.resize(2-(i!=0||j!=1));
			sm[o][i][j].vc[0]=(i==0&&j==1?MN:a[l]*j);
			if(i==0&&j==1)sm[o][i][j].vc[1]=(i==0&&j==1?a[l]:MN);
		}
		tudd(o);
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,o<<1);
	build(mid+1,r,o<<1|1);
	for(int i=0;i<2;++i)for(int j=0;j<2;++j)
		sm[o][i][j]=mini(hebing(sm[o<<1][i][0],sm[o<<1|1][0][j]),hebing(sm[o<<1][i][1],sm[o<<1|1][1][j]));
	tudd(o);
}
int az[50005];
int id[50005],SM[1000005],S2[1000005],ls[1000005],rs[1000005],tot=0;
void add(int x,int y,int l,int r,int u,int v){
	if(l==r){
		SM[y]=SM[x]+v,S2[y]=S2[x]+1;
		return;
	}
	int mid=(l+r)>>1;
	ls[y]=ls[x],rs[y]=rs[x];
	if(u<=mid)add(ls[x],ls[y]=++tot,l,mid,u,v);
	else add(rs[x],rs[y]=++tot,mid+1,r,u,v);
	SM[y]=SM[ls[y]]+SM[rs[y]],S2[y]=S2[ls[y]]+S2[rs[y]];
}
pair<int,int>query(int x,int y,int l,int r,int ll,int rr){
	if(l>=ll&&r<=rr)return make_pair(SM[y]-SM[x],S2[y]-S2[x]);
	int mid=(l+r)>>1;
	int a1=0,a2=0;
	if(mid>=ll){
		auto au=query(ls[x],ls[y],l,mid,ll,rr);
		a1+=au.first,a2+=au.second;
	}
	if(mid<rr){
		auto au=query(rs[x],rs[y],mid+1,r,ll,rr);
		a1+=au.first,a2+=au.second;
	}
	return make_pair(a1,a2);
}
pair<long long,int>X[2];
int C;
#define ccv sm[o][i][j].cv
void apply(int o){
	pair<long long,int>X1[2]={{-1e18,0},{-1e18,0}};
	for(int i=0;i<2;++i)for(int j=0;j<2;++j){
		int wz=upper_bound(ccv.begin(),ccv.end(),-C)-ccv.begin();
		int k=sm[o][i][j].vc.size()-wz-1;
		long long h1=X[i].first+sm[o][i][j].vc[k]+1ll*k*C;
		int h2=X[i].second-k;
		X1[j]=max(X1[j],make_pair(h1,h2));
	}
	X[0]=X1[0],X[1]=X1[1];
}
vector<int>ap;
void quer(int l,int r,int o,int ll,int rr){
	if(l>=ll&&r<=rr){
		ap.emplace_back(o);
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=ll)quer(l,mid,o<<1,ll,rr);
	if(mid<rr)quer(mid+1,r,o<<1|1,ll,rr);
}
pair<long long,int>suan(int l,int r,int c){
	if(c>0){
		int dy=upper_bound(az+1,az+n+1,-c)-az;
		if(dy>n)return make_pair(0,0);
		auto au=query(id[l-1],id[r],1,n,dy,n);
		long long he=au.first+1ll*c*au.second;
		int gs=au.second;
		return make_pair(he,gs);
	}
	X[0]=make_pair(0,0);X[1]=make_pair(-1e18,0);C=c;
	for(auto o:ap)apply(o);
	auto au=max(X[0],X[1]);
	return make_pair(au.first,-au.second);
}
int main(){
//	int aa=clock();
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]),az[i]=a[i];
	sort(az+1,az+n+1);
	for(int i=1;i<=n;++i){
		int wz=lower_bound(az+1,az+n+1,a[i])-az;
		add(id[i-1],id[i]=++tot,1,n,wz,a[i]);
	}
	build(1,n,1);
//	cerr<<1.0*(clock()-aa)/CLOCKS_PER_SEC<<endl;
	while(q--){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		ap.clear();
		quer(1,n,1,l,r);
		int L=-(r-l+1)*35000,R=-L;
		while(L<=R){
			int mid=(0ll+L+R+2*ZZ)/2-ZZ;
			auto au=suan(l,r,mid);
			if(au.second<k)L=mid+1;
			else R=mid-1;
		}
		auto au=suan(l,r,R);
		long long ans=au.first-1ll*R*k;
		printf("%lld\n",ans);
	}
//	cerr<<1.0*(clock()-aa)/CLOCKS_PER_SEC<<endl;
	return 0;
}