#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=2e9;
int n;
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];int pos[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(int&pos,vector<int>&vt,int k)//斜率为 k 的直线切到的凸包 
	{ 
		while(pos<vt.size()-1&&vt[pos+1]-k*(pos+1)>vt[pos]-k*pos)pos++;
		return vt[pos]-k*pos;
//		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(pos[x][i][j],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;
	}
	void clear(){memset(pos,0,sizeof(pos));}
}
struct Q{int l,r,k,id;};
int ans[N];
vector<pair<pii,vector<Q> > >vt[2];
int tv[N];
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int qq;cin>>n>>qq;
	for(int i=1;i<=n;i++)cin>>a[i];
	Seg::build(1,1,n,a);
	vector<Q>st;
	for(int i=1,l,r,k;i<=qq;i++)cin>>l>>r>>k,st.push_back({l,r,k,i});
	vt[0].push_back(mk(mk(-inf,inf),st));
	while(!vt[0].empty())
	{
		vt[1].clear();Seg::clear();
//		reverse(vt[0].begin(),vt[0].end());
		for(auto st:vt[0])
		{
			int l=st.fi.fi,r=st.fi.se;
//			cout<<l<<' '<<r<<';';
			vector<Q>vec=st.se,lc,rc;
			if(l==r){for(auto x:vec)ans[x.id]=Seg::query(1,x.l,x.r,1,n,l)[0][0]+l*x.k;continue;}
			int md=l+r>>1;
			for(int i=0;i<vec.size();i++)tv[i]=Seg::query(1,vec[i].l,vec[i].r,1,n,md+1)[0][0]+(md+1)*vec[i].k;
			for(int i=0;i<vec.size();i++) 
			{
				int lv=Seg::query(1,vec[i].l,vec[i].r,1,n,md)[0][0]+md*vec[i].k,rv=tv[i];
				if(lv==rv){ans[vec[i].id]=lv;continue;}
				else if(lv>rv)rc.push_back(vec[i]);else lc.push_back(vec[i]);
			}
			if(!rc.empty())vt[1].push_back(mk(mk(md+1,r),rc));
			if(!lc.empty())vt[1].push_back(mk(mk(l,md),lc));
		}
//		cout<<endl;
		swap(vt[0],vt[1]);
	}
	for(int i=1;i<=qq;i++)cout<<ans[i]<<endl;
//	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 1
-1 1 -4 5 -1 4
2 5 1
*/