#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int N=35005;
const int inf=0x3f3f3f3f;
inline int rd()
{
	int x=0; bool f=1;
	char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())
		if(ch=='-') f=0;
	for(;ch>='0'&&ch<='9';ch=getchar())
		x=x*10+(ch^48);
	return f?x:-x;
}
int a[N];
vector<int> vec[N<<2][2][2];
#define mid ((l+r)>>1)
vector<int> merge(const vector<int> &va,const vector<int> &vb)
{
	if(va.empty()||vb.empty()) return vector<int>();
	vector<int> wow;
	for(int i=1;i<va.size();i++)
		wow.push_back(va[i]-va[i-1]);
	for(int i=1;i<vb.size();i++)
		wow.push_back(vb[i]-vb[i-1]);
	sort(wow.begin(),wow.end(),greater<int>());
	vector<int> res;
	res.push_back(va[0]+vb[0]);
	for(int v:wow)
		res.push_back(res.back()+v);
	
	// for(int v:va) cout<<v<<' '; cout<<endl;
	// for(int v:vb) cout<<v<<' '; cout<<endl;
	// for(int v:res) cout<<v<<' '; cout<<endl;
	return res;
}
void build(int l,int r,int p)
{
	if(l==r)
	{
		vec[p][0][0].push_back(0);
		vec[p][1][1].push_back(-inf);
		vec[p][1][1].push_back(a[l]);
		return;
	}
	build(l,mid,p<<1);
	build(mid+1,r,p<<1|1);
	for(int u=0;u<=1;u++) //[u,nu][nv,v]
		for(int v=0;v<=1;v++)
		{
			auto &f=vec[p][u][v];
			for(int nu=0;nu<=1;nu++)
				for(int nv=0;nv<=1;nv++)
				{
					vector<int> now=merge(vec[p<<1][u][nu],vec[p<<1|1][nv][v]);
					if(now.empty()) continue;
					for(int i=f.size();i<now.size();i++)
						f.push_back(now[i]);
					for(int i=1;i<now.size();i++)
						f[i]=max(f[i],now[i]);
					if(nu==1&&nv==1)
					{
						for(int i=1;i<now.size();i++)
							now[i-1]=now[i];
						now.pop_back();
						for(int i=1;i<now.size();i++)
							f[i]=max(f[i],now[i]);
					}
				}
				// cout<<"out "<<l<<' '<<r<<' '<<u<<" "<<v<<endl;
				// 		for(int v:f)
				// 			cout<<v<<' ';cout<<endl;
		}
	// cout<<l<<" "<<r<<endl;
	// for(int v:vec[p][1][1])
	// 	cout<<v<<' ';
	// cout<<endl;
}
int D;
pair<int,int> cmx(pair<int,int> a,pair<int,int> b)
{
	if(a.first==b.first)
		return a.second<b.second?a:b;
	return a.first>b.first?a:b;
}
struct Node
{
	pair<int,int> a[2][2];
	Node()
	{ memset(a,0,sizeof(a)); }
	Node operator+(const Node b) const
	{
		Node c;
		for(int u=0;u<=1;u++) //[u,nu][nv,v]
			for(int v=0;v<=1;v++)
				for(int nu=0;nu<=1;nu++)
					for(int nv=0;nv<=1;nv++)
					{
						// cout<<a[u][nu].first<<' '<<a[u][nu].second<<' '<<a[nv][v].first<<' '<<a[nv][v].second<<(nv&&nu?"bing":"no")<<endl;
						pair<int,int> tmp(a[u][nu].first+b.a[nv][v].first,a[u][nu].second+b.a[nv][v].second);
						c.a[u][v]=cmx(c.a[u][v],tmp);
						if(nu&&nv)
						{
							tmp.first-=D,tmp.second--;
							c.a[u][v]=cmx(c.a[u][v],tmp);
						}
					}
		return c;
	}
};
pair<int,int> fnd(const vector<int> &v)
{
	// for(int vv:v)
	// 	cout<<vv<<' ';cout<<endl;
	int l=0,r=v.size()-1;
	while(l<r)
	{
		int m=(l+r)>>1;
		if(v[m+1]-v[m]>-D)
			l=mid+1;
		else
			r=mid;
	}
	// cout<<v[l]+l*D<<' '<<l<<endl;
	return {v[l]+l*D,l};
}
Node que(int l,int r,int p,int ld,int rd)
{
	if(l>=ld&&r<=rd)
	{
		Node wow;
		for(int u=0;u<=1;u++)
			for(int v=0;v<=1;v++)
				wow.a[u][v]=fnd(vec[p][u][v]);
		return wow;
	}
	if(ld<=mid&&rd>mid)
		return que(l,mid,p<<1,ld,rd)+que(mid+1,r,p<<1|1,ld,rd);
	if(ld<=mid)
		return que(l,mid,p<<1,ld,rd);
	else
		return que(mid+1,r,p<<1|1,ld,rd);
}
#undef mid
int n,q;
pair<int,int> solve(int l,int r)
{
	Node wow=que(1,n,1,l,r);
	return cmx(cmx(wow.a[0][0],wow.a[0][1]),cmx(wow.a[1][0],wow.a[1][1]));
}
signed main()
{
	n=rd(),q=rd();
	for(int i=1;i<=n;i++)
		a[i]=rd();
	build(1,n,1);
	while(q--)
	{
		int ql=rd(),qr=rd(),k=rd();
		int l=-1e9,r=1e9;
		int ans=0;
		while(l<=r)
		{
			D=(l+r)>>1;
			pair<int,int> now=solve(ql,qr);
			// cout<<D<<" "<<now.first<<' '<<now.second<<endl;
			if(now.second==k)
			{
				ans=now.first-k*D;
				break;
			}
			if(now.second<k)
				ans=now.first-k*D,l=D+1;
			else
				r=D-1;
		}
		printf("%lld\n",ans);
	}
	return 0;
}