#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c^'0'),c=getchar();
    return x*f;
}
#define ll long long
int n,m;
int a[50005];
struct node{
    ll x;int y;
    bool operator <(const node &b)const{return x!=b.x?x<b.x:y<b.y;}
    bool operator >(const node &b)const{return x!=b.x?x>b.x:y>b.y;}
};
const node operator +(const node &x,const node &y){return (node){x.x+y.x,x.y+y.y};}
struct nade{
    node a[2][2];
};
const nade operator +(const nade &x,const nade &y){
    nade res;
    for(int i=0;i<2;i++)for(int j=0;j<2;j++)res.a[i][j]=max(x.a[i][0]+y.a[0][j],x.a[i][1]+y.a[1][j]);
    return res;
}
vector<ll> tree[200005][2][2];
vector<ll> merge(vector<ll> &x,vector<ll> &y,int f){
    vector<ll> res;if(f)res.push_back(-0x3f3f3f3f);
    int i=0,j=0;res.push_back(x[0]+y[0]);
    while(i+1<x.size()||j+1<y.size()){
        if(i+1<x.size()&&(j+1==y.size()||x[i+1]-x[i]>=y[j+1]-y[j]))i++;
        else j++;
        res.push_back(x[i]+y[j]);
    }
    return res;
}
vector<ll> getmax(vector<ll> x,vector<ll> y){
    vector<ll> res;
    if(x.size()>y.size())swap(x,y);
    for(int i=0;i<x.size();i++)res.push_back(max(x[i],y[i]));
    for(int i=x.size();i<y.size();i++)res.push_back(y[i]);
    return res;
}
node calc(vector<ll> &x,ll X,int f){
    int l=0,r=x.size()-1;
    while(l<r){
        int mid1=l+r>>1,mid2=mid1+1;
        if(x[mid1]-2*mid1*X>x[mid2]-2*mid2*X)r=mid1;
        else l=mid2;
    }
    return (node){x[l]-(2*l+f)*X,2*l+f};
}
void build(int k,int l,int r){
    if(l==r){
        tree[k][0][0]={0,a[l]};
        tree[k][0][1]={a[l]};
        tree[k][1][0]={a[l]};
        tree[k][1][1]={a[l]};
        // printf("k=%d l=%d r=%d\n",k,l,r);
        // for(int i=0;i<2;i++)for(int j=0;j<2;j++,puts(""))for(int x:tree[k][i][j])printf("%d ",x);puts("");
        return;
    }
    int mid=l+r>>1;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    for(int i=0;i<2;i++)for(int j=0;j<2;j++)
        tree[k][i][j]=getmax(merge(tree[k*2][i][0],tree[k*2+1][0][j],i&j),merge(tree[k*2][i][1],tree[k*2+1][1][j],!i&!j));
    // printf("k=%d l=%d r=%d\n",k,l,r);
    // for(int i=0;i<2;i++)for(int j=0;j<2;j++,puts(""))for(int x:tree[k][i][j])printf("%d ",x);puts("");
}
vector<int> vec;
void query(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y){
        vec.push_back(k);
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)query(k*2,l,mid,x,y);
    if(y>mid)query(k*2+1,mid+1,r,x,y);
}
node solve(ll X){
    nade res;
    for(int i=0;i<2;i++)for(int j=0;j<2;j++)res.a[i][j]=calc(tree[vec[0]][i][j],X,i^j);
    for(int k=1;k<vec.size();k++){
        nade p;
        for(int i=0;i<2;i++)for(int j=0;j<2;j++)p.a[i][j]=calc(tree[vec[k]][i][j],X,i^j);
        res=res+p;
    }
    return res.a[0][0];
}
int main(){
    freopen("impact.in","r",stdin);
    freopen("impact.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read()*2;
    build(1,1,n);
    cerr<<"time: "<<clock()*1000./CLOCKS_PER_SEC<<"ms"<<endl;
    while(m--){
        int l=read(),r=read(),k=read();
        vec.clear();
        query(1,1,n,l,r);
        ll L=-1e9,R=1e9;
        while(L<R){
            ll mid=L+R+1>>1;
            node res=solve(mid);
            // printf("X=%lld res=(%lld %d)\n",mid,res.x,res.y);
            if(res.y>=2*k)L=mid;
            else R=mid-1;
        }
        node res=solve(L);
        // printf("X=%lld res=(%lld %d)\n",L,res.x,res.y);
        printf("%lld\n",(res.x)/2+k*L);
    }
    cerr<<"time: "<<clock()*1000./CLOCKS_PER_SEC<<"ms"<<endl;
    return 0;
}