#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
struct Query{
int l, r, idx;
Query(){}
Query(int l, int r, int idx): l(l), r(r), idx(idx){}
};
struct maxSegmentTree{
ll tree[800002];
void init(int i, int l, int r, ll A[]){
if(l==r){
tree[i] = A[l];
return;
}
int m = (l+r)>>1;
init(i*2, l, m, A);
init(i*2+1, m+1, r, A);
tree[i] = max(tree[i*2], tree[i*2+1]);
}
int biggerLim(int i, int l, int r, int x, ll lim, int dir){ /// bigger than lim / dir=0: left, dir=1: right
if(tree[i] <= lim) return dir==0 ? l-1 : r+1;
if(l==r) return l;
int m = (l+r)>>1;
if(dir == 0){
if(x<=m) return biggerLim(i*2, l, m, x, lim, dir);
int tmp = biggerLim(i*2+1, m+1, r, x, lim, dir);
if(tmp > m) return tmp;
return biggerLim(i*2, l, m, x, lim, dir);
}
else{
if(m<x) return biggerLim(i*2+1, m+1, r, x, lim, dir);
int tmp = biggerLim(i*2, l, m, x, lim, dir);
if(tmp <= m) return tmp;
return biggerLim(i*2+1, m+1, r, x, lim, dir);
}
}
} maxSeg;
struct lazySegmentTree{
struct Fenwick{
int n;
ll tree[400002];
void addRange(int x, ll y){
while(x){
tree[x] += y;
x -= x&-x;
}
}
ll rangeSum(int x){
ll ret = 0;
while(x<=n){
ret += tree[x];
x += x&-x;
}
return ret;
}
} mul, add;
int n;
void init(int _n){
mul.n = add.n = n = _n;
}
void addRange(int x, ll y){
x = min(x, n);
mul.addRange(x, y);
add.addRange(n, y*x);
add.addRange(x, -y*x);
}
inline ll rangeSum(int x){
if(x<=0) return 0;
return mul.rangeSum(x) * x + add.rangeSum(x);
}
inline ll rangeSum(int l, int r){
return rangeSum(r) - rangeSum(l-1);
}
} segRight, segDiag;
int n, q;
ll arr[200002];
vector<Query> query[200005];
ll ans[200002];
vector<pair<int, ll> > triangle[200005];
void input();
void makeTriangles();
void sweep();
int main(){
input();
makeTriangles();
sweep();
for(int i=1; i<=q; i++) printf("%lld\n", ans[i]);
}
void input(){
scanf("%d %d", &n, &q);
for(int i=1; i<=n; i++){
scanf("%lld", &arr[i]);
}
for(int i=1; i<=q; i++){
int t, l, r;
scanf("%d %d %d", &t, &l, &r);
query[t+1].push_back(Query(l, r, i));
}
}
void makeTriangles(){
maxSeg.init(1, 1, n, arr);
for(int i=1; i<=n; i++){
triangle[1].push_back(make_pair(i, arr[i]));
int rLim = maxSeg.biggerLim(1, 1, n, i+1, arr[i]-1, 1);
if(i<n && rLim <= n && 1<=rLim-i+1 && rLim-i+1<=n+1)
triangle[rLim-i+1].push_back(make_pair(rLim, -arr[i]));
int lLim = maxSeg.biggerLim(1, 1, n, i-1, arr[i], 0);
if(i>1 && lLim >= 1 && 1<=i-lLim+1 && i-lLim+1<=n+1)
triangle[i-lLim+1].push_back(make_pair(i, -arr[i]));
if(i<n && i>1 && rLim <= n && lLim >= 1 &&
1<=(rLim - i + 1) + (i - lLim + 1) - 1 && (rLim - i + 1) + (i - lLim + 1) - 1 <= n+1){
triangle[(rLim - i + 1) + (i - lLim + 1) - 1].push_back(make_pair(rLim, arr[i]));
}
}
}
void sweep(){
segRight.init(n);
segDiag.init(2*n+1);
for(int i=1; i<=n+1; i++){
for(auto pr: triangle[i]){
segRight.addRange(pr.first - 1, -pr.second);
segDiag.addRange((n+1) + pr.first - i, pr.second);
}
for(auto qr: query[i]){
ans[qr.idx] += segRight.rangeSum(qr.l, qr.r);
ans[qr.idx] += segDiag.rangeSum((n+1) + qr.l - i, (n+1) + qr.r - i);
}
}
}
