#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; }