#include <bits/stdc++.h>
using namespace std;
enum event_type {
start_decreasing, stop_increasing, become_zero
};
struct fenwick_tree{
vector<long long> bit;
fenwick_tree(int n) : bit(n + 1, 0) {}
void update(int id, long long val){
for(; id < (int)bit.size(); id += id & (-id)) bit[id] += val;
}
long long query(int id){
long long sum = 0;
for(; id > 0; id -= id & (-id)) sum += bit[id];
return sum;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int N, Q;
cin >> N >> Q;
vector<int> S(N + 1), L(N + 1), R(N + 1), stop_inc(N + 1), start_dec(N + 1);
stack<int> st;
for(int i = 1; i <= N; ++i){
cin >> S[i];
}
for(int i = 1; i <= N; ++i){
while(!st.empty() && S[st.top()] <= S[i]) st.pop();
L[i] = (st.empty() ? -(2 * N + 1) : st.top());
st.push(i);
}
while(!st.empty()) st.pop();
for(int i = N; i >= 1; --i){
while(!st.empty() && S[st.top()] < S[i]) st.pop();
R[i] = (st.empty() ? + (N + 1) : st.top());
st.push(i);
}
vector<vector<tuple<int, int, int>>> queries(N + 2);
for(int i = 0; i < Q; ++i){
int t, l, r;
cin >> t >> l >> r;
queries[t + 1].emplace_back(l, r, i);
}
vector<vector<tuple<event_type, int>>> sweep(N + 2);
for(int i = 1; i <= N; ++i){
{ //start decreasing
int t = i - L[i];
start_dec[i] = t;
if(1 <= t && t <= N + 1){
sweep[t].emplace_back(start_decreasing, i);
}
}
{ //stop increasing
int t = R[i] - i;
stop_inc[i] = t;
if(1 <= t && t <= N + 1){
sweep[t].emplace_back(stop_increasing, i);
}
}
{ //become zero
int t = start_dec[i] + stop_inc[i] - 1;
if(1 <= t && t <= N + 1){
sweep[t].emplace_back(become_zero, i);
}
}
}
int B = 32 - __builtin_clz(N);
vector<vector<int>> prev(B, vector<int>(N + 1, -1));
for(int i = 1; i <= N; ++i){
prev[0][i] = L[i];
}
for(int i = 1; i < B; ++i){
for(int j = 1; j <= N; ++j){
prev[i][j] = prev[i - 1][j];
if(prev[i][j] > 0) prev[i][j] = prev[i - 1][prev[i][j]];
}
}
auto find_exact_value = [&](int i, int t) -> int{
int cur = i;
for(int b = B - 1; b >= 0; --b){
if(prev[b][cur] > 0 && i - prev[b][cur] <= t){
cur = prev[b][cur];
}
}
return cur;
};
fenwick_tree ft1(N), ft2(N), ft3(N), ft4(N);
for(int i = 1; i <= N; ++i){
ft1.update(i, S[i]);
}
vector<long long> answer(Q);
for(int t = 1; t <= N + 1; ++t){
auto calculate_prefix = [&](int r) -> long long{
int pos = find_exact_value(r, t - 1);
long long A = ft1.query(pos - 1);
long long B = ft2.query(pos - 1);
long long C = ft3.query(pos - 1);
long long D = ft4.query(pos - 1);
long long sum_part = A * t + B;
long long loss_part = D * t - C;
int num_inc = L[pos] + t;
long long extra_part = 1LL * S[pos] * (r - max(pos, num_inc) + 1);
return sum_part - loss_part + extra_part;
};
for(auto [l, r, i] : queries[t]){
answer[i] = calculate_prefix(r) - (l > 1 ? calculate_prefix(l - 1) : 0);
}
for(auto [e, i] : sweep[t]){
if(e == start_decreasing){
ft3.update(i, 1LL * S[i] * start_dec[i]);
ft4.update(i, S[i]);
} else if(e == stop_increasing){
ft1.update(i, -S[i]);
ft2.update(i, 1LL * S[i] * stop_inc[i]);
} else if(e == become_zero){
ft2.update(i, -1LL * S[i] * stop_inc[i]);
ft3.update(i, -1LL * S[i] * start_dec[i]);
ft4.update(i, -S[i]);
} else assert(false);
}
}
for(int i = 0; i < Q; ++i){
cout << answer[i] << '\n';
}
return 0;
}
