#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 2e5 + 5;
int prv[mn], nxt[mn], A[mn], B[mn], G[mn];
vector<tuple<int,int,int>> qry[mn], update[mn];
ll S[mn], ans[mn];
struct BIT {
vector<ll> idp, idpmul, dp, dpmul;
BIT (int sz) : idp(sz + 1), idpmul(sz + 1), dp(sz + 1), dpmul(sz + 1) {}
int p (int k) { return k & -k; }
void updateIDP (int pos, ll delta) {
for (int k = pos; k < idp.size(); k += p(k))
idp[k] += delta, idpmul[k] += delta * S[pos];
}
void updateDP (int pos, ll delta) {
for (int k = pos; k < dp.size(); k += p(k))
dp[k] += delta, dpmul[k] += delta * S[pos];
}
ll getNode (int k, ll T) { return idp[k] + dp[k] * T; }
ll preSum (int k, ll T) {
ll ans = 0;
for (; k; k -= p(k))
ans += idpmul[k] + dpmul[k] * T;
return ans;
}
ll sumFirstK (int target, ll T) {
if (target == 0) return 0;
int position = 0, sumCur = 0;
for (int mask = 1 << 17; mask; mask >>= 1) {
if ((position | mask) >= idp.size()) continue;
if (sumCur + getNode(position | mask, T) < target)
position |= mask, sumCur += getNode(position, T);
}
return preSum(position, T) + (target - sumCur) * S[position + 1];
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// input
int N, Q; cin >> N >> Q;
for (int i = 1; i <= N; i++) cin >> S[i];
for (int i = 0; i < Q; i++) {
int T, L, R; cin >> T >> L >> R;
qry[T].emplace_back(L, R, i);
}
// precompute prv, nxt
vector<int> st;
for (int i = 1; i <= N; i++) {
while (st.size() && S[st.back()] < S[i]) st.pop_back();
prv[i] = (st.size() ? st.back() : -1e9), st.push_back(i);
}
st.clear();
for (int i = N; i >= 1; i--) {
while (st.size() && S[st.back()] <= S[i]) st.pop_back();
nxt[i] = (st.size() ? st.back() : 1e9), st.push_back(i);
}
// compute A, B, G and create sweep-line events
for (int i = 1; i <= N; i++) {
A[i] = min(nxt[i] - i, i - prv[i]);
B[i] = max(nxt[i] - i, i - prv[i]);
G[i] = nxt[i] - prv[i];
// update independent part
update[0].emplace_back(i, 1, 0);
if (A[i] <= N) update[A[i]].emplace_back(i, A[i] - 1, 0);
if (B[i] <= N) update[B[i]].emplace_back(i, G[i] - 1 - A[i], 0);
if (G[i] <= N) update[G[i]].emplace_back(i, 0 - G[i] + 1, 0);
// update dependent part
update[0].emplace_back(i, 1, 1);
if (A[i] <= N) update[A[i]].emplace_back(i, -1, 1);
if (B[i] <= N) update[B[i]].emplace_back(i, -1, 1);
if (G[i] <= N) update[G[i]].emplace_back(i, 1, 1);
}
// perform sweep line
BIT tree(N);
for (int T = 0; T <= N; T++) {
// process updates
for (auto [idx, delta, dpd] : update[T]) {
if (dpd) tree.updateDP(idx, delta);
else tree.updateIDP(idx, delta);
}
// process queries
for (auto [L, R, idx] : qry[T])
ans[idx] = tree.sumFirstK(R, T) - tree.sumFirstK(L - 1, T);
}
// output queries
for (int i = 0; i < Q; i++) cout << ans[i] << "\n";
return 0;
}
