#include <bits/stdc++.h>
#include <bits/extc++.h>
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
if(pvaspace) b << " "; pvaspace=true;\
b << pva;\
}\
b << "\n";}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;
const ll MOD = 1000000007;
const ll MAX = 2147483647;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.F << ',' << p.S << ')';
}
ll ifloor(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a < 0) return (a - b + 1) / b;
else return a / b;
}
ll iceil(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a > 0) return (a + b - 1) / b;
else return a / b;
}
int lowbit(int x){
return x & -x;
}
struct BIT{
vector<ll> bit;
void init(int n){
bit.resize(n + 1);
}
void modify(int x, ll v){
for(; x < bit.size(); x += lowbit(x)) bit[x] += v;
}
ll query(int x){
x = min(x, (int)bit.size() - 1);
ll ans = 0;
for(; x > 0; x -= lowbit(x)) ans += bit[x];
return ans;
}
};
struct BITSUM{
BIT bit1, bit2;
int offset;
void init(int n){
bit1.init(2 * n + 1);
bit2.init(2 * n + 1);
offset = n;
}
void modify(int x, ll v){
x += offset;
bit1.modify(x, v);
bit2.modify(x, x * v);
}
void modify(int l, int r, ll v){
modify(l, v);
modify(r + 1, -v);
}
ll query(int x){
x += offset;
return (x + 1) * bit1.query(x) - bit2.query(x);
}
ll query(int l, int r){
return query(r) - query(l - 1);
}
void off(){
modify(0, 0, query(1, 1));
offset--;
}
};
int main(){
StarBurstStream
int n, q;
cin >> n >> q;
vector<ll> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
vector<vector<pii>> qry(n + 1);
for(int i = 1; i <= q; i++){
int t, l, r;
cin >> t >> l >> r;
qry[l - 1].eb(mp(t, -i));
qry[r].eb(mp(t, i));
}
BITSUM bit1, bit2, bit3;
bit1.init(n); bit2.init(n); bit3.init(n);
ll con = 0;
vector<int> pr(n + 1, -1);
vector<int> sz(n + 1, 1);
auto remove = [&](int i){
if(pr[i] == -1) return;
ll dp = i - pr[i] - 1;
ll da = a[pr[i]] - a[i];
bit1.modify(1, sz[i] + dp, -da);
bit2.modify(1, sz[i] + dp, da);
sz[pr[i]] += sz[i];
};
auto add = [&](int i){
if(pr[i] == -1) return;
ll dp = i - pr[i] - 1;
ll da = a[pr[i]] - a[i];
bit1.modify(1, 1 + dp, da);
bit3.modify(1, dp, da);
con += -dp * da;
};
auto query = [&](int T){
return bit1.query(T) + bit2.query(T) + bit3.query(T + 1, n) + con;
};
deque<int> dq;
vector<ll> ans(q + 1);
for(int i = 1; i <= n; i++){
while(!dq.empty() && a[dq.back()] <= a[i]){
remove(dq.back());
dq.pob;
}
bit1.off();
pr[i] = dq.empty() ? -1 : dq.back();
add(i);
dq.eb(i);
con += a[i];
/*cerr << "test " << i << " " << con << "\n";
printv(dq, cerr);
for(int i = 1; i <= n; i++) cerr << bit1.query(i) << " ";
cerr << "\n";
for(int i = 1; i <= n; i++) cerr << bit2.query(i) << " ";
cerr << "\n";
for(int i = 1; i <= n; i++) cerr << bit3.query(i) << " ";
cerr << "\n";*/
for(auto j : qry[i]){
ll tmp = query(j.F);
if(j.S > 0) ans[j.S] += tmp;
else ans[-j.S] -= tmp;
}
}
for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
return 0;
}
