#include <bits/stdc++.h>
#define pii pair<int, int>
#define ti3 tuple<int, int, int>
#define ti4 tuple<int, int, int, int>
#define int long long
// We are dancing on fire ~~ ~ Seunghee, Dun Dun Dance
using namespace std;
// Notice that in a 2d array (pos, t), each number will form a parallelogram in the array.
// for eg, sample input (look at 6):
// 93265
// 99366
// 99966
// 99996
// 99999
// for each parallelogram, we can decompose it into 3 triangles starting from t=0.
// for eg, 6 in sample input:
// .XX6Y
// ..X66
// ...66
// ....6
// .....
// left point of triangle is 1 + (largest leftmost idx >= a[i]), right point of triangle is
// (smallest rightmost idx > a[i]) - 1;
// updating a triangle = updating a parallelogram [l, inf) starting from t=0 and
// updating a rectangle [r+1, inf) starting from t=0
// so actual update on triangle will be the difference b/w the 2 intersections.
// ie. actual_range_sum0(l, r) = range_sum_par0(l, r) - range_sum_rect0(l, r);
// note: if rightmost / leftmost elem does not exist just use a very big/small number
// Moreover, all (actual) updates are parallelograms, so
// B..XX
// XC..X
// abc
// notice that b to c = a to b (B and C are equal unless the parallelogram of B ends there)
// so range_sum(l, r, t) = range_sum_par(l, r, t) - range_sum_rect(l, r, t)
// = range_sum_par0(l - h + 1, r - h + 1, t) - range_sum_rect0(l, r)
// when h is the height of the parallelogram, which is basically t + 1(0-indexed)
// to ensure that B and C are equal (I think? - but we should remove those out of range triangles anyways)
// we sweep line by T, and remove triangles that are out of range (height < t);
int arr[200005], L[200005], R[200005], ans[200005];
vector<ti3> heights[200005];
vector<ti3> queries[200005];
struct fenwick{
int N;
int fw[400010], fw2[400010];
int off = 200002;
fenwick(int N): N(N){
memset(fw, 0, sizeof fw);
memset(fw2, 0, sizeof fw2);
}
void update(int x, int y, int v) { //inclusive
x += off; y += off;
for (int tx=x; tx <= N; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1);
for (int ty=y+1; ty <= N; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y;
}
int sum (int x) {
int res = 0;
for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx];
return res;
}
int range_sum(int x, int y) { //inclusive
x += off; y += off;
return sum(y)-sum(x-1);
}
} *parfw = new fenwick(400005), *rectfw = new fenwick(400005);
int n;
void tri(int l, int r, int v, bool upd){
if (l > r) return;
parfw->update(l, n+1, v);
rectfw->update(r+1, n+1, v);
if (upd){
int height = r-l+1;
if (height <= n) heights[height].push_back({l, r, -v});
}
}
main(){
int q; cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> arr[i];
stack<int> nums;
for (int i = 1; i <= n; i++){
while (!nums.empty() && arr[nums.top()] < arr[i]) nums.pop();
L[i] = (nums.empty()?-n-1:nums.top());
nums.push(i);
}
while (!nums.empty()) nums.pop();
for (int i = n; i > 0; i--){
while (!nums.empty() && arr[nums.top()] <= arr[i]) nums.pop();
R[i] = (nums.empty()?n+1:nums.top());
nums.push(i);
}
for (int i = 1; i <= n; i++){
tri(L[i]+1, R[i]-1, arr[i], true); // large triangle
tri(L[i]+1, i-1, -arr[i], true); // small triangle
tri(i+1, R[i]-1, -arr[i], true); // small triangle
}
for (int i = 1; i <= q; i++){
int t, l, r; cin >> t >> l >> r;
queries[t].push_back({l, r, i});
}
// time starts from 0, so triangles with heights t or below should be removed
for (int t = 1; t <= n; t++){
for (auto [l, r, v]: heights[t]) tri(l, r, v, false);
for (auto [l, r, i]: queries[t]) ans[i] = parfw->range_sum(l-t, r-t) - rectfw->range_sum(l, r);
}
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
