#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 4e5 + 5;
ll a[mn], lb[mn], rb[mn], small[mn], big[mn], all[mn], ans[mn];
vector<pii> event[mn];
vector<tt> qry[mn];
struct BIT {
vector<ll> tr;
BIT (int sz) : tr(sz + 1) {}
int p (int k) { return k & -k; }
void update (int k, ll val) {
for (; k < tr.size(); k += p(k)) tr[k] += val;
}
ll preSum (int k, ll ans = 0) {
for (; k; k -= p(k)) ans += tr[k];
return ans;
}
int get (int k) { return tr[k]; }
} cntOne(mn), sumOne(mn), freqTwo(mn), sumTwo(mn), cntThree(mn), freqThree(mn), sumThree(mn), sumFreqThree(mn);
int cntGet (int k, int T) {
return cntOne.get(k) * (T + 1) + freqTwo.get(k) + freqThree.get(k) - cntThree.get(k) * T;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, q; cin >> n >> q;
for (int i = n + 1; i <= 2 * n; i++) cin >> a[i];
for (int i = 0; i < q; i++) {
int T, L, R; cin >> T >> L >> R;
qry[T].emplace_back(n + L - 1 - T, i, -1);
qry[T].emplace_back(n + R - T, i, 1);
}
a[0] = a[2 * n + 1] = INT_MAX;
stack<int> st;
st.push(0);
for (int i = 1; i <= 2 * n; i++) {
while (make_pair(a[st.top()], st.top()) <= make_pair(a[i], i)) st.pop();
lb[i] = st.top() + 1; st.push(i);
}
while (st.size()) st.pop(); st.push(2 * n + 1);
for (int i = 2 * n; i >= 1; i--) {
while (make_pair(a[st.top()], st.top()) <= make_pair(a[i], i)) st.pop();
rb[i] = st.top() - 1; st.push(i);
}
for (int i = 1; i <= 2 * n; i++) {
small[i] = i - lb[i] + 1, big[i] = rb[i] - i + 1;
all[i] = rb[i] - lb[i] + 1;
if (small[i] > big[i]) swap(small[i], big[i]);
event[small[i]].emplace_back(i, 1); // switch to small[i]
event[big[i]].emplace_back(i, 2); // switch to all[i] - T
event[all[i]].emplace_back(i, 3); // switch to 0
cntOne.update(i, 1);
sumOne.update(i, a[i]);
}
for (int T = 1; T <= n; T++) {
for (pii it : event[T]) {
int pos, type; tie(pos, type) = it;
if (type == 1) {
cntOne.update(pos, -1);
sumOne.update(pos, -a[pos]);
freqTwo.update(pos, small[pos]);
sumTwo.update(pos, a[pos] * small[pos]);
}
else if (type == 2) {
freqTwo.update(pos, -small[pos]);
sumTwo.update(pos, -a[pos] * small[pos]);
cntThree.update(pos, 1);
freqThree.update(pos, all[pos]);
sumThree.update(pos, a[pos]);
sumFreqThree.update(pos, a[pos] * all[pos]);
}
else if (type == 3) {
cntThree.update(pos, -1);
freqThree.update(pos, -all[pos]);
sumThree.update(pos, -a[pos]);
sumFreqThree.update(pos, -a[pos] * all[pos]);
}
}
for (tt it : qry[T]) {
int P, id, multi; tie(P, id, multi) = it;
int ub = 0, cur = 0;
for (int msk = 1 << 18; msk > 0; msk >>= 1)
if ((ub | msk) <= 2 * n && cur + cntGet(ub | msk, T) <= P)
ub |= msk, cur += cntGet(ub, T);
ll accumulated = sumOne.preSum(ub) * (T + 1) + sumTwo.preSum(ub) + sumFreqThree.preSum(ub) - sumThree.preSum(ub) * T;
if (ub < 2 * n) accumulated += a[ub + 1] * (P - cur);
ans[id] += accumulated * multi;
}
}
for (int i = 0; i < q; i++) cout << ans[i] << "\n";
return 0;
}
