#include <bits/stdc++.h>
using namespace std;
#ifndef lisie_bimbi
#define endl '\n'
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi2,fma")
#endif
using ll = long long;
const ll inf = 1'000'000'000'000'000'000;
const int N = 200'010;
#define int long long
struct node{
int cnt;
ll sum;
ll ans;
};
node merge(node a, node b){
node ans;
ans.cnt = a.cnt + b.cnt;
ans.sum = a.sum + b.sum;
ans.ans = a.ans + b.ans + a.sum * b.cnt;
return ans;
}
struct segtree{
node d[4 * N];
void build(int u = 0, int l = 0, int r = N){
d[u] = {r - l, 0, 0};
if(l + 1 != r){
int m = (l + r) / 2;
build(u * 2 + 1, l, m);
build(u * 2 + 2, m, r);
}
}
int ql, qr, ind;
ll dd;
node gg(int u, int l, int r){
if((ql >= r) || (qr <= l)){
return {0, 0, 0};
}
if((ql <= l) && (r <= qr)){
return d[u];
}
int m = (l + r) / 2;
return merge(gg(u * 2 + 1, l, m), gg(u * 2 + 2, m, r));
}
void uu(int u, int l, int r){
if(l + 1 == r){
d[u].sum += dd;
d[u].ans += dd;
}else{
int m = (l + r) / 2;
if(ind < m){
uu(u * 2 + 1, l, m);
}else{
uu(u * 2 + 2, m, r);
}
d[u] = merge(d[u * 2 + 1], d[u * 2 + 2]);
}
}
int get(int ql1, int qr1){
ql = ql1;
qr = qr1;
auto ans = gg(0, 0, N);
ql = 0;
qr = ql1;
return ans.ans + ans.cnt * gg(0, 0, N).sum;
}
void update(int ind1, ll dd1){
ind = ind1;
dd = dd1;
uu(0, 0, N);
}
void vivo(int u = 0, int l = 0, int r = N){
if(l + 1 == r){
cout << d[u].sum << ' ';
}else{
int m = (l + r) / 2;
vivo(u * 2 + 1, l, m);
vivo(u * 2 + 2, m, r);
}
if(u == 0){
cout << endl;
}
}
};
struct running_segtree{
node d[8 * N];
void build(int u = 0, int l = 0, int r = 2 * N){
d[u] = {r - l, 0, 0};
if(l + 1 != r){
int m = (l + r) / 2;
build(u * 2 + 1, l, m);
build(u * 2 + 2, m, r);
}
}
int ql, qr, ind;
ll dd;
node gg(int u, int l, int r){
if((ql >= r) || (qr <= l)){
return {0, 0, 0};
}
if((ql <= l) && (r <= qr)){
return d[u];
}
int m = (l + r) / 2;
return merge(gg(u * 2 + 1, l, m), gg(u * 2 + 2, m, r));
}
void uu(int u, int l, int r){
if(l + 1 == r){
d[u].sum += dd;
d[u].ans += dd;
}else{
int m = (l + r) / 2;
if(ind < m){
uu(u * 2 + 1, l, m);
}else{
uu(u * 2 + 2, m, r);
}
d[u] = merge(d[u * 2 + 1], d[u * 2 + 2]);
}
}
int shift = N;
void step(){
shift--;
}
int get(int ql1, int qr1){
ql = ql1 + shift;
qr = qr1 + shift;
auto ans = gg(0, 0, 2 * N);
ql = 0;
qr = ql1 + shift;
return ans.ans + ans.cnt * gg(0, 0, 2 * N).sum;
}
void update(int ind1, ll dd1){
ind = ind1 + shift;
dd = dd1;
uu(0, 0, 2 * N);
}
vector<int> pepe;
void vivo(int u = 0, int l = 0, int r = 2 * N){
if(u == 0){
pepe.clear();
}
if(l + 1 == r){
pepe.push_back(d[u].sum);
}else{
int m = (l + r) / 2;
vivo(u * 2 + 1, l, m);
vivo(u * 2 + 2, m, r);
}
if(u == 0){
for(int i = shift; i < shift + N; i++){
cout << pepe[i] << ' ';
}
cout << endl;
}
}
};
segtree st;
running_segtree st1;
struct query{
int l;
int r;
int ind;
};
int get(int l, int r){
return st.get(l, r) + st1.get(l, r);
}
void solve(){
st.build();
st1.build();
int n, q;
cin >> n >> q;
vector<ll> a(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}
vector<vector<query>> qq(n + 1);
for(int i = 0; i < q; i++){
int l, r, t;
cin >> t >> l >> r;
l--;
qq[t].push_back({l, r, i});
}
vector<vector<pair<int, int>>> events(n + 2), events1(n + 2);
vector<int> left(n), right(n);
deque<pair<ll, int>> z = {{inf, - n - 2}};
for(int i = 0; i < n; i++){
while(z.back().first <= a[i]){
z.pop_back();
}
left[i] = z.back().second;
z.push_back({a[i], i});
}
z = {{inf, n}};
for(int i = n - 1; i >= 0; i--){
while(z.back().first < a[i]){
z.pop_back();
}
right[i] = z.back().second;
z.push_back({a[i], i});
}
for(int i = 0; i < n; i++){
int l = left[i], r = right[i];
events[0].emplace_back(i, a[i]);
events[min(i - l - 1, n + 1)].emplace_back(i, -a[i]);
events[r - i - 1].emplace_back(r, -a[i]);
events[min(r - l - 1, n + 1)].emplace_back(r, a[i]);
events1[0].emplace_back(i + 1, -a[i]);
events1[r - i - 1].emplace_back(r, a[i]);
events1[min(i - l - 1, n + 1)].emplace_back(i, a[i]);
events1[min(r - l - 1, n + 1)].emplace_back(r, -a[i]);
}
vector<ll> ans(q);
for(int i = 0; i <= n; i++){
// cout << "xxxxxxxxxxxxxxxxxxxxxxx " << i << endl;
for(auto [ind, dd] : events[i]){
st.update(ind, dd);
}
for(auto [ind, dd] : events1[i]){
st1.update(ind, dd);
}
// st.vivo();
// st1.vivo();
// cout << endl;
for(auto [l, r, ind] : qq[i]){
// cout << "aaaa " << l << ' ' << r << ' ' << ind << endl;
// cout << st.get(l, r) << ' ' << st1.get(l, r) << endl;
ans[ind] = get(l, r);
}
st1.step();
}
for(auto i : ans){
cout << i << endl;
}
}
signed main(){
#ifdef lisie_bimbi
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
#endif
cin.tie(nullptr)->sync_with_stdio(false);
int t = 1;
//cin >> t;
while(t--){
solve();
}
}
