#include <bits/stdc++.h>
using namespace std;
#define dbg(x) "[" << #x << " = " << (x) << "]"
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;
}
void debug(){
cout << "[";
for(int i = 1; i < (int)bit.size(); ++i){
cout << query(i) - query(i - 1);
if(i + 1 == (int)bit.size()) cout << "]\n";
else cout << ", ";
}
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
#endif // LOCAL
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);
}
// for(int i = 1; i <= N; ++i){
// cout << "LR : " << i << " " << L[i] << ' ' << R[i] << '\n';
// }
/*
- Consider frequency table on ranges
Event :
Part 1 : Start increasing
Part 2, 3 : (i - L[i]) : Start decreasing, (R[i] - i) : Stop increasing (May be 3, 2 or 2, 3)
Part 4 : (R[i] - L[i] - 1) Become zero when the first S[j] larger than S[i] reach the stop-increasing point
the points for S[i] after T (remember to plus 1) is
f(i, S) = max(0, S[i] * min(T, stop_inc[i]) - S[i] * max(0, T - start_dec[i]))
For T - start_dec[i] >= 0 => T >= start_dec[i], we can calculate this part by let S[i] * T * cnt_on - S[i] * sum start_dec[pos]
ok now we have to handle the case for this equation :
min(T, stop_inc[i]) >= max(0, T - start_dec[i])
consider when T < stop_inc[i] => T >= max(0, T - start_dec[i]) <=> T >= T - start_dec[i] (ez)
consider when T > stop_inc[i] => stop_inc[i] >= max(0, T - start_dec[i]) <=> stop_inc[i] >= T - start_dec[i] <=> stop_inc[i] + start_dec[i] >= T
*/
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;
// cout << "become zero : " << i << " -> " << t << '\n';
if(1 <= t && t <= N + 1){
sweep[t].emplace_back(become_zero, i);
}
}
// cout << i << "(" << start_dec[i] << ", " << stop_inc[i] << ")\n";
}
// cout << '\n';
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;
};
// vector<long long> answer(Q);
// for(int t = 2; t <= N + 1; ++t){
// long long sum = 0;
// for(auto [l, r, id] : queries[t]){
// long long sum = 0;
// for(int i = l; i <= r; ++i){
// cout << max(0, S[i] * (min(t, stop_inc[i]) - max(0, t - start_dec[i]))) << ' ';
// sum += max(0, S[i] * (min(t, stop_inc[i]) - max(0, t - start_dec[i])));
// }
//
// answer[id] = sum;
// }
// }
//
// for(int i = 0; i < Q; ++i) cout << answer[i] << '\n';
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){
// cout << "at : " << t << '\n';
auto calculate_prefix = [&](int r) -> long long{
// cout << dbg(r) << ' ';
int pos = find_exact_value(r, t - 1);
// cout << dbg(pos) << ' ';
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);
assert(extra_part >= 0);
// cout << dbg(sum_part) << dbg(loss_part) << dbg(extra_part) << '\n';
// cout << dbg(A) << dbg(B) << dbg(C) << dbg(D) << '\n';
// cout << dbg(sum_part - loss_part + extra_part) << '\n' << '\n';
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){
// cout << "start decreasing : " << i << '\n';
ft3.update(i, 1LL * S[i] * start_dec[i]);
ft4.update(i, S[i]);
} else if(e == stop_increasing){
// cout << "stop increasing : " << i << '\n';
ft1.update(i, -S[i]);
ft2.update(i, 1LL * S[i] * stop_inc[i]);
} else if(e == become_zero){
// cout << "become zero : " << i << '\n';
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);
}
// cout << '\n';
// cout << "that's all\n\n";
}
for(int i = 0; i < Q; ++i){
cout << answer[i] << '\n';
}
return 0;
}
