#include <iostream>
#include <vector>
#include <array>
using namespace std;
#define int long long
const int N = (1<<19) + 1;
vector<array<int, 3>> Quer[N], ev[N];
int Ans[N], Sum[2][N<<1], Laz[2][N<<1], nxt[N], prv[N], a[N];
void Push(int t, int cur, int lc, int rc, int sz){
Sum[t][lc] += Laz[t][cur] * sz, Laz[t][lc] += Laz[t][cur];
Sum[t][rc] += Laz[t][cur] * sz, Laz[t][rc] += Laz[t][cur];
Laz[t][cur] = 0;
}
void Add(int t, int l, int r, int v, int cur = 1, int st = 1, int en = N){
if (l >= en or r <= st)
return;
if (l <= st and r >= en){
Sum[t][cur] += v * (en - st);
Laz[t][cur] += v;
return;
}
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
Push(t, cur, lc, rc, mid - st);
Add(t, l, r, v, lc, st, mid);
Add(t, l, r, v, rc, mid, en);
Sum[t][cur] = Sum[t][lc] + Sum[t][rc];
}
int get(int t, int l, int r, int cur = 1, int st = 1, int en = N){
if (l >= en or r <= st)
return 0;
if (l <= st and r >= en)
return Sum[t][cur];
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
Push(t, cur, lc, rc, mid - st);
return get(t, l, r, lc, st, mid) + get(t, l, r, rc, mid, en);
}
void PushT(int l, int r, int v, bool b){
Add(0, l, N, v);
Add(1, r, N, -v);
if (b)
ev[r - l].push_back({l, r, -v});
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, q, o;
cin>>n>>q;
o = n + 5;
for (int i=1;i<=n;i++)
cin>>a[i+o];
a[1] = a[n+o+1] = 1e9 + 7;
vector<int> v;
for (int i=1;i<=n+o+1;i++){
while (v.size() > 0 and a[v.back()] < a[i])
nxt[v.back()] = i, v.pop_back();
v.push_back(i);
}
v = {};
for (int i=n+o+1;i;i--){
while (v.size() > 0 and a[v.back()] <= a[i])
prv[v.back()] = i, v.pop_back();
v.push_back(i);
}
for (int i=o+1;i<=n+o;i++){
PushT(prv[i]+1, nxt[i], a[i], 1);
PushT(prv[i]+1, i, -a[i], 1);
PushT(i+1, nxt[i], -a[i], 1);
}
for (int i=1, t, l, r;i<=q;i++){
cin>>t>>l>>r;
Quer[t].push_back({i, l+o, r+o});
}
for (int t=0;t<=n;t++){
for (auto [l, r, v] : ev[t])
PushT(l, r, v, 0);
for (auto [ind, l, r] : Quer[t])
Ans[ind] = get(0, l-t, r-t+1) + get(1, l, r+1);
}
for (int i=1;i<=q;i++)
cout<<Ans[i]<<endl;
}
