#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define int long long
using namespace std;
const int N=5e4+100,inf=1e9;
int n,q;
int a[N];
vector<int>operator*(const vector<int>&x,const vector<int>&y)
{
	int n=x.size(),m=y.size();vector<int>z(n+m-1,-inf);
	for(int i=0,j=0;i+j<(int)z.size();)
	{
		z[i+j]=max(z[i+j],x[i]+y[j]);
		if(i==(int)x.size()-1)j++;else if(j==(int)y.size()-1)i++;
		else if(x[i+1]+y[j]>x[i]+y[j+1])i++;else j++;
	}
	return z;
}
namespace Seg
{
	#define ls (x<<1)
	#define rs (x<<1|1)
	#define mid ((L+R)>>1)
	vector<int>mt[N<<2][2][2];
	struct Node
	{
		int mt[2][2];
		Node(){memset(mt,0xcf,sizeof(mt));}
		auto&operator[](const int&x){return mt[x];}
	};
	void build(int x,int L,int R,int*a)
	{
		if(L==R)
		{
			mt[x][0][0]=vector<int>{0,a[L]};
			mt[x][0][1]=mt[x][1][0]=mt[x][1][1]=vector<int>{-inf,a[L]};
			return;
		}
		build(ls,L,mid,a);build(rs,mid+1,R,a);
		for(int i:{0,1})for(int j:{0,1})
		{
			auto f=mt[ls][i][0]*mt[rs][0][j],g=mt[ls][i][1]*mt[rs][1][j];
			for(int k=0;k<(int)g.size()-1;k++)f[k]=max(f[k],g[k+1]);
			mt[x][i][j]=f;
		}
	}
	int query(vector<int>&vt,int k)//斜率为 k 的直线切到的凸包 
	{
		int l=0,r=vt.size()-2;
		while(l<r)
		{
			int md=l+r>>1,lv=vt[md]-k*md,rv=vt[md+1]-k*(md+1);
			if(lv<rv)l=md+1;else r=md;
		}
		return max(vt[l]-k*l,vt.back()-(int)(vt.size()-1)*k);
	}
	Node query(int x,int l,int r,int L,int R,int k)
	{
		if(l<=L&&R<=r){Node t;for(int i:{0,1})for(int j:{0,1})t[i][j]=query(mt[x][i][j],k);return t;}
		if(r<=mid)return query(ls,l,r,L,mid,k);
		if(l>mid)return query(rs,l,r,mid+1,R,k);
		Node a=query(ls,l,r,L,mid,k),b=query(rs,l,r,mid+1,R,k),c;
		for(int i:{0,1})for(int j:{0,1})c[i][j]=max(a[i][0]+b[0][j],a[i][1]+b[1][j]+k);
		return c;
	}
}
signed main()
{
//	freopen("impact4_1.in","r",stdin);
//	freopen("impact.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	Seg::build(1,1,n,a);
	while(q--)
	{
		int l,r,k;cin>>l>>r>>k;
		int L=-inf,R=inf;
		auto check=[&](const int&k){return Seg::query(1,l,r,1,n,k)[0][0];};
		while(L<R)
		{
			int md=L+R>>1;
			int lv=check(md)+md*k,rv=check(md+1)+(md+1)*k;	
			if(lv==rv){L=md;break;}
			else if(lv>rv)L=md+1;
			else R=md;
		}
		cout<<check(L)+L*k<<endl;
	}
	return 0;
}
/*
6 5
-1 1 -4 5 -1 4
2 5 1
*/