#include<bits/stdc++.h>
using namespace std;
vector<int>tr[140005][2][2];
int a[35005],inf=1e9,n,x,y,m,k;pair<int,int>val[2],tmp[2];
vector<int> merge(vector<int>x,vector<int>y)
{
	vector<int>res;res.emplace_back(x[0]+y[0]);
	int p1=1,p2=1;
	while(p1<x.size()&&p2<y.size())
	{
		if(x[p1]-x[p1-1]>y[p2]-y[p2-1])res.emplace_back(res.back()+x[p1]-x[p1-1]),p1++;
		else res.emplace_back(res.back()+y[p2]-y[p2-1]),p2++;
	}
	while(p1<x.size())res.emplace_back(res.back()+x[p1]-x[p1-1]),p1++;
	while(p2<y.size())res.emplace_back(res.back()+y[p2]-y[p2-1]),p2++;
	return res;
}
void build(int k,int l,int r)
{
	if(l==r)
	{
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)tr[k][i][j].resize(2);
		tr[k][0][0][0]=0;tr[k][0][0][1]=a[l];tr[k][0][1][0]=-inf;tr[k][0][1][1]=a[l];
		tr[k][1][0][0]=-inf;tr[k][1][0][1]=a[l];tr[k][1][1][0]=-inf;tr[k][1][1][1]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);build(k<<1|1,mid+1,r);
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)
		{
			auto c1=merge(tr[k<<1][i][0],tr[k<<1|1][0][j]);
			auto c2=merge(tr[k<<1][i][1],tr[k<<1|1][1][j]);
			tr[k][i][j].resize(r-l+2);
			for(int p=0;p<c1.size()-1;p++)tr[k][i][j][p]=max(c1[p],c2[p+1]);
			tr[k][i][j][c1.size()-1]=c1.back();
		}
	}
}
void query(int k,int l,int r,int x,int y,int w)
{
	if(x<=l&&r<=y)
	{
		tmp[0]=val[0];tmp[1]=val[1];val[0]=val[1]={-inf,0};
		for(int i=0;i<2;i++)
		{
			for(int j=0;j<2;j++)
			{
				int pl=0,pr=tr[k][i][j].size()-2;
				pair<int,int> now={-inf,0}; 
				while(pl<=pr)
				{
					int mid=(pl+pr)>>1;
					now=max(now,make_pair(tr[k][i][j][mid]-mid*w,mid));
					now=max(now,make_pair(tr[k][i][j][mid+1]-(mid+1)*w,mid+1));
					if(tr[k][i][j][mid]-mid*w>tr[k][i][j][mid+1]-(mid+1)*w)pr=mid-1;
					else pl=mid+1;
				}
				val[j]=max(val[j],make_pair(tmp[i].first+now.first,tmp[i].second+now.second-(i==1)));
			}
		}
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)query(k<<1,l,mid,x,y,w);
	if(y>mid)query(k<<1|1,mid+1,r,x,y,w);
}
pair<int,int> solve(int mid)
{
	val[0]={0,0};val[1]={0,0};
	query(1,1,n,x,y,mid); 
	return max(val[0],val[1]);
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	while(m--)
	{
		cin>>x>>y>>k;
		int l=-35000,r=35000,pos=35000;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(solve(mid).second>=k)pos=mid,l=mid+1;
			else r=mid-1;
		}
		pair<int,int> now=solve(pos);
		cout<<now.first+k*pos<<'\n';
	}
	return 0;
}