#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#define all(x) x.begin(), x.end()
using namespace std;
const int N = 200005;
struct RURQ{
long long tree1[400014];
long long tree2[400014];
inline void update(long long l, long long r, long long v){
l += N, r += N;
int L = l, R = r;
for(r++;r <= 2*N;r += (r & -r)){
tree1[r] -= v;
tree2[r] -= R*v;
}
for(;l <= 2*N;l += (l & -l)){
tree1[l] += v;
tree2[l] += (L-1)*v;
}
}
inline long long query(long long r){
long long R = r;
long long ans = 0;
for(;r;r -= (r & -r)){
ans += R * tree1[r];
ans -= tree2[r];
}
return ans;
}
inline long long query(int l, int r){
l += N, r += N;
return query(r) - query(l-1);
}
} vert, diag;
struct QU{ int l, r; long long v; }; //Query or Update
vector<QU> queries[200005];
vector<QU> updates[200005];
int arr[200005];
long long ans[200005];
int L[200005];
int R[200005];
void tri(int l, int r, long long v){
if(r < l) return;
diag.update(l, N, v);
vert.update(r+1, N, -v);
if(r-l+1 < N) updates[r-l+1].push_back({l, r, v});
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n, Q; cin >> n >> Q;
for(int i = 1;i <= n;i++) cin >> arr[i];
for(int i = 1;i <= Q;i++){
int t, l, r; cin >> t >> l >> r;
queries[t].push_back({l,r,i});
}
stack<int> S;
for(int i = 1;i <= n;i++){
while(!S.empty() && arr[S.top()] < arr[i]) S.pop();
if(S.empty()) L[i] = -N+1;
else L[i] = S.top();
S.push(i);
}
while(!S.empty()) S.pop();
for(int i = n;i >= 0;i--){
while(!S.empty() && arr[S.top()] <= arr[i]) S.pop();
if(S.empty()) R[i] = N-1;
else R[i] = S.top();
S.push(i);
}
for(int i = 1;i <= n;i++){
tri(L[i]+1,R[i]-1,arr[i]);
tri(L[i]+1,i-1,-arr[i]);
tri(i+1,R[i]-1,-arr[i]);
}
for(int t = 1;t <= n;t++){
for(QU u : updates[t]){
diag.update(u.l, N, -u.v);
vert.update(u.r+1, N, u.v);
}
for(QU q : queries[t]){
ans[q.v] = diag.query(q.l - t, q.r - t) + vert.query(q.l, q.r);
}
}
for(int i = 1;i <= Q;i++) cout << ans[i] << "\n";
return 0;
}
