#include <bits/stdc++.h>
using namespace std;
int n,q,pod=1,nale[200001],napr[200001];
pair<pair<int,int>,pair<int,int>>pyta[200001];
int drzemax[1000001],pocz,kon;
int itmi,itma,gmi,gma,gze;
pair<int,int>zmmin[200001],zmmax[200001],zmzer[200001];
stack<int>stos;
long long odp[200001],drze[1000001][2],ciag[200002];
int znajdz(int ter,int odte,int dote)
{
if(ter>=pod)
return ter-pod;
if(odte>=pocz&&dote<=kon)
{
if(drzemax[((ter<<1)^1)]>=drzemax[(ter<<1)])
return znajdz(((ter<<1)^1),((odte+dote)>>1)+1,dote);
else
return znajdz((ter<<1),odte,((odte+dote)>>1));
}
int pom1=0,pom2=0;
if(((odte+dote)>>1)+1<=kon)
pom1=znajdz(((ter<<1)^1),((odte+dote)>>1)+1,dote);
if(((odte+dote)>>1)>=pocz)
pom2=znajdz((ter<<1),odte,((odte+dote)>>1));
if(ciag[pom1]>=ciag[pom2])
return pom1;
else
return pom2;
}
long long naprze(int odte,int dote,long long te)
{
long long ret=0;
odte+=pod;
dote+=pod;
while(odte<dote)
{
if(odte%2==0)
odte>>=1;
else
{
ret+=drze[odte][0]+drze[odte][1]*te;
odte>>=1;
++odte;
}
if(dote%2==1)
dote>>=1;
else
{
ret+=drze[dote][0]+drze[dote][1]*te;
dote>>=1;
--dote;
}
}
if(odte==dote)
{
ret+=drze[dote][0]+drze[dote][1]*te;
}
return ret;
}
int main()
{
scanf("%d%d",&n,&q);
while(pod<=n)
pod<<=1;
for(int i=1;i<=n;++i)
{
scanf("%lld",&ciag[i]);
drze[i+pod][0]=ciag[i];
drze[i+pod][1]=ciag[i];
drzemax[i+pod]=ciag[i];
while(!stos.empty())
{
if(ciag[stos.top()]>ciag[i])
break;
stos.pop();
}
if(!stos.empty())
nale[i]=stos.top();
stos.push(i);
}
while(!stos.empty())
stos.pop();
ciag[n+1]=1000000001;
stos.push(n+1);
for(int i=n;i>0;--i)
{
while(!stos.empty())
{
if(ciag[stos.top()]>=ciag[i])
break;
stos.pop();
}
napr[i]=stos.top()-1;
stos.push(i);
zmmin[itmi].second=i;
zmmin[itmi].first=napr[i]-i;
++itmi;
if(nale[i])
{
zmmax[itma].second=i;
zmmax[itma].first=i-nale[i];
zmzer[itma].second=i;
zmzer[itma].first=napr[i]-nale[i];
++itma;
}
}
for(int i=pod-1;i>=0;--i)
{
drzemax[i]=max(drzemax[(i<<1)],drzemax[((i<<1)^1)]);
drze[i][0]=drze[(i<<1)][0]+drze[((i<<1)^1)][0];
drze[i][1]=drze[(i<<1)][1]+drze[((i<<1)^1)][1];
}
for(int i=0;i<q;++i)
{
scanf("%d%d%d",&pyta[i].first.first,&pyta[i].second.first,&pyta[i].second.second);
pyta[i].first.second=i;
}
sort(pyta,pyta+q);
sort(zmmin,zmmin+itmi);
sort(zmmax,zmmax+itma);
sort(zmzer,zmzer+itma);
for(int i=0;i<q;++i)
{
for(int j=gmi;j<itmi;++j)
{
if(zmmin[j].first>pyta[i].first.first)
break;
++gmi;
int ter=zmmin[j].second+pod;
drze[ter][0]-=ciag[ter-pod]*(ter-pod);
drze[ter][1]-=ciag[ter-pod];
drze[ter][0]+=ciag[ter-pod]*napr[ter-pod];
ter/=2;
while(ter)
{
drze[ter][0]=drze[(ter<<1)][0]+drze[((ter<<1)^1)][0];
drze[ter][1]=drze[(ter<<1)][1]+drze[((ter<<1)^1)][1];
ter>>=1;
}
}
for(int j=gma;j<itma;++j)
{
if(zmmax[j].first>pyta[i].first.first)
break;
++gma;
int ter=zmmax[j].second+pod;
drze[ter][0]+=ciag[ter-pod]*(ter-pod-1);
drze[ter][1]-=ciag[ter-pod];
drze[ter][0]-=ciag[ter-pod]*nale[ter-pod];
ter/=2;
while(ter)
{
drze[ter][0]=drze[(ter<<1)][0]+drze[((ter<<1)^1)][0];
drze[ter][1]=drze[(ter<<1)][1]+drze[((ter<<1)^1)][1];
ter>>=1;
}
}
for(int j=gze;j<itma;++j)
{
if(zmzer[j].first>pyta[i].first.first)
break;
++gze;
int ter=zmzer[j].second+pod;
drze[ter][0]=0;
drze[ter][1]=0;
drze[ter][0]=0;
ter/=2;
while(ter)
{
drze[ter][0]=drze[(ter<<1)][0]+drze[((ter<<1)^1)][0];
drze[ter][1]=drze[(ter<<1)][1]+drze[((ter<<1)^1)][1];
ter>>=1;
}
}
pocz=max(1,pyta[i].second.first-pyta[i].first.first)+pod;
kon=pyta[i].second.first+pod;
int p1=znajdz(1,pod,pod+pod-1);
pocz=max(1,pyta[i].second.second-pyta[i].first.first)+pod;
kon=pyta[i].second.second+pod;
int p2=znajdz(1,pod,pod+pod-1);
if(p1==p2)
odp[pyta[i].first.second]=(pyta[i].second.second-pyta[i].second.first+1)*ciag[p1];
else
{
odp[pyta[i].first.second]=naprze(p1+1,p2-1,pyta[i].first.first);
odp[pyta[i].first.second]+=(min(napr[p1],p1+pyta[i].first.first)-pyta[i].second.first+1)*ciag[p1];
if(nale[p2])
odp[pyta[i].first.second]+=(pyta[i].second.second-max(p2-1,nale[p2]+pyta[i].first.first))*ciag[p2];
else
odp[pyta[i].first.second]+=(pyta[i].second.second-p2+1)*ciag[p2];
}
}
for(int i=0;i<q;++i)
printf("%lld\n",odp[i]);
return 0;
}
