#include <bits/stdc++.h>
typedef long long ll;
#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
using namespace std;
#define lp pos<<1
#define rp (lp)^1
#define cur (*this)[pos]
#define lc (*this)[lp]
#define rc (*this)[rp]
struct node{
int l, r, sz = 0;
ll val = 0, tag = 0;
};
struct TREE: vector<node> {
void init(int l, int r, int pos){
cur = {l, r, r-l+1, 0, 0};
if(cur.sz>1){
int m = (l+r)>>1;
init(l, m, lp);
init(m+1, r, rp);
}
}
inline void push(int pos){
lc.tag += cur.tag;
lc.val += cur.tag*lc.sz;
rc.tag += cur.tag;
rc.val += cur.tag*rc.sz;
cur.tag = 0;
}
void update(int l, int r, int pos, ll x){
if(l==cur.l && r==cur.r){
cur.tag += x;
cur.val += x*cur.sz;
return;
}
push(pos);
if(r<rc.l) update(l, r, lp, x);
else if(l>lc.r) update(l, r, rp, x);
else update(l, lc.r, lp, x), update(rc.l, r, rp, x);
cur.val = lc.val + rc.val;
}
ll query(int l, int r, int pos){
if(l==cur.l && r==cur.r) return cur.val;
push(pos);
if(r<rc.l) return query(l, r, lp);
else if(l>lc.r) return query(l, r, rp);
else return query(l, lc.r, lp)+query(rc.l, r, rp);
}
} t1, t2; // vertical, diagonal
int n;
inline ll query(int l, int r, int t){
return t1.query(l, r, 1)+t2.query(n+l-t, n+r-t, 1);
}
int main(){
fastio
/*freopen("02-01.txt", "r", stdin);
freopen("00-test.txt", "w", stdout);*/
int q;
cin >> n >> q;
vector<ll> s(n+1);
for(int i=1; i<=n; i++) cin >> s[i];
//building segment tree
vector<int> l(n+1), r(n+1), stk;
//nearest larger fire
for(int i=1; i<=n; i++){
while(!stk.empty() && s[stk.back()]<s[i]) stk.pop_back();
l[i] = stk.empty()?-n:stk.back();
stk.push_back(i);
}
stk.clear();
for(int i=n; i>0; i--){
while(!stk.empty() && s[stk.back()]<=s[i]) stk.pop_back();
r[i] = stk.empty()?n+1:stk.back();
stk.push_back(i);
}
/*for(int i=1; i<=n; i++) cout << l[i] << " \n"[i==n];
for(int i=1; i<=n; i++) cout <<r[i] << " \n"[i==n];*/
int ed1 = n+1, ed2 = (n<<1)^1;
t1.resize(ed1<<2), t2.resize(ed2<<2);
t1.init(1, ed1, 1), t2.init(1, ed2, 1);
vector<vector<tuple<int, int, ll>>> swp(n+1); //t1+x, t2-x
//sweeping line
for(int i=1; i<=n; i++) t1.update(i, ed1, 1, s[i]), t2.update(n+i+1, ed2, 1, -s[i]);
auto f = [&](int L, int R, ll val){
L++;
int t = R-L;
if(t<=n) swp[t].push_back({R, n+L, val});
};
for(int i=1; i<=n; i++){
f(l[i], r[i], s[i]);
f(l[i], i, -s[i]);
f(i, r[i], -s[i]);
}
/*for(int i=0; i<=n; i++){
cout << i << " : ";
for(const auto &tup: swp[i])
cout << '{' << get<0>(tup) << ", " << get<1>(tup) << ", " << get<2>(tup) << "} ";
cout << '\n';
}
cout << "s[0] : ";
for(int i=1; i<=n; i++) cout << query(i, i, 0) << " \n"[i==n];*/
//processing queries
vector<ll> ans(q);
vector<vector<tuple<int, int, int>>> qry(n+1);
for(int i=0; i<q; i++){
int T, L, R;
cin >> T >> L >> R;
qry[T].push_back({L, R, i});
}
for(int i=0; i<=n; i++){
for(const auto &tup: swp[i]){
t1.update(get<0>(tup), ed1, 1, get<2>(tup));
t2.update(get<1>(tup), ed2, 1, -get<2>(tup));
}
for(const auto &tup: qry[i])
ans[get<2>(tup)] = query(get<0>(tup), get<1>(tup), i);
}
for(int i=0; i<q; i++) cout << ans[i] << '\n';
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
