#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> ii;
typedef pair<int,ii> bro;
class LE {
private:
vi nx,pr,se;
int n;
public:
LE() {
}
LE(int sz) {
n = sz;
nx.assign(n,0);
pr.assign(n,0);
se.assign(n,1);
for(int i=0;i<n;i++) {
if(i > 0) {
pr[i] = i-1;
}
if(i < n-1) {
nx[i] = i+1;
}
}
nx[n-1] = pr[0] = -1;
}
int nex(int u) {
return nx[u];
}
int pre(int u) {
return pr[u];
}
int rem(int u) {
//cout << "e " << u << '\n';
int res = pr[u];
//cout << pr[u] << " -> " << nx[u] << '\n';
if(pr[u] != -1) {
nx[pr[u]] = nx[u];
}
if(nx[u] != -1) {
pr[nx[u]] = pr[u];
}
nx[u] = pr[u] = -1;
se[u] = 0;
return res;
}
int has(int u) {
return se[u];
}
};
class ST {
private:
vl st;
int n,h;
public:
ST() {
}
ST(int sz) {
n = 1;
h = 1;
while(n < sz) {n<<=1;h++;}
st.assign(2*n,0);
}
void up(int p, ll val) {
p += n;
st[p] += val;
while(p > 1) {
st[p>>1] = st[p]+st[p^1];
p >>= 1;
}
}
ll get(int l, int r) {
ll res = 0;
for(l+=n,r+=n;l<r;l>>=1,r>>=1) {
if(l&1) {
res += st[l];
l++;
}
if(r&1) {
--r;
res += st[r];
}
}
return res;
}
ll kth(ll num) {
ll p = 1;
for(int i=1;i<h;i++) {
p <<= 1;
if(st[p] < num) {
num -= st[p];
p++;
}
}
return p-n;
}
};
LE les,leg;
ST sa,sb;
vl w,fr;
vi act,mo;
vector<ii> so;
bool proc(ii& seg) {
if(seg.second == seg.first) {return false;}
int ra = seg.first, rb = seg.second;
sa.up(ra,1);
sb.up(ra,w[ra]);
fr[ra]++;
sa.up(rb,-1);
sb.up(rb,-w[rb]);
fr[rb]--;
if(fr[rb] == 0) {
seg.second = les.rem(rb);
}
return true;
}
void merge() {
vi nu;
for(int i=0;i<mo.size();i++) {
if(!leg.has(mo[i])) {continue;}
int id = mo[i];
int re = so[id].second;
int reg = leg.nex(id);
while(reg != -1 && w[reg] <= w[re]) {
leg.rem(reg);
so[id].second = so[reg].second;
reg = leg.nex(id);
re = so[id].second;
}
if(so[id].second != so[id].first) {
act.push_back(id);
}
}
mo.clear();
}
void succ() {
vi nu;
for(int i=0;i<act.size();i++) {
int u = act[i];
if(!leg.has(u)) {continue;}
proc(so[u]);
int nt = leg.nex(u);
if(w[so[u].second] >= w[nt]) {
mo.push_back(u);
} else if(so[u].first != so[u].second) {
nu.push_back(u);
}
}
act = nu;
}
ll ksu(int p) {
if(p == 0) {return 0;}
int num = sa.kth(p);
ll res = sb.get(0,num);
ll re = p-sa.get(0,num);
res += w[num]*re;
return res;
}
const int MN = 200200;
vector<bro> qv[MN];
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int n,q;
cin >> n >> q;
les = LE(n);
leg = LE(n);
sa = ST(n);
sb = ST(n);
fr.assign(n,1);
for(int i=0;i<n;i++) {
ll t;
cin >> t;
w.push_back(t);
so.push_back({i,i});
mo.push_back(i);
sa.up(i,1);
sb.up(i,w[i]);
}
for(int i=0;i<q;i++) {
int a,b,c;
cin >> a >> b >> c;
b--;
qv[a].push_back({i,{b,c}});
}
vl res(q,0);
merge();
for(int i=0;i<=n;i++) {
/*
for(int j=0;j<n;j++) {
int u = sa.kth(j+1);
cout << w[u] << " ";
}
cout << '\n';
*/
for(int j=0;j<qv[i].size();j++) {
int idx = qv[i][j].first;
ii co = qv[i][j].second;
res[idx] = ksu(co.second)-ksu(co.first);
}
succ();
merge();
}
for(int i=0;i<q;i++) {
cout << res[i] << '\n';
}
}
