#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)
#define ALL(v) (v).begin(), (v).end()
template<typename T> bool maximize(T &x, const T &y) {
if (x < y) {x = y; return 1;}
return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
if (x > y) {x = y; return 1;}
return 0;
}
const int maxn = 2e5+5, lg = 19;
struct SPT{
int sz, st[maxn][lg];
void init(int _n, int a[]) {
sz = _n;
memset(st, 0, sizeof(st));
for (int i = 1; i <= sz; i++) {
st[i][0] = a[i];
}
for (int j = 1; j < lg; j++) {
if (MASK(j) >= sz) break;
for (int i = 1; i+MASK(j)-1 <= sz; i++) {
st[i][j] = max(st[i][j-1], st[i+MASK(j-1)][j-1]);
}
}
}
int query(int l, int r) {
int k = __lg(r-l+1);
return max(st[l][k], st[r-MASK(k)+1][k]);
}
};
struct query{
int l, r, t, id;
ll ans;
query(const int &_l, const int &_r, const int &_t, const int &_id) {
l = _l;
r = _r;
t = _t;
id = _id;
}
};
int n, q, a[maxn];
//vector<query> qu;
namespace sub1{
const int maxn1 = 205;
bool check(){
return max(n, q) <= maxn1;
}
int b[maxn1];
void solve() {
while (q--) {
int t, l, r;
cin >> t >> l >> r;
for (int i = n; i; i--) {
b[i] = a[i];
for (int j = i+1; j <= min(r, i+t); j++) {
maximize(b[j], a[i]);
}
}
ll ans = 0;
for (int i = l; i <= r; i++) {
ans += b[i];
}
cout << ans << "\n";
}
}
}
namespace sub5{
SPT spt;
ll ps1[maxn], ps2[maxn]; ///r-(l-1), l-(r+1)
void solvequery(int t, int l, int r) {
ll ans = 0;
//bs range1
int k1, k2;
int mamid = 0; //mid range
if (r-t < l-1) {
if (l-1 > 0) mamid = spt.query(max(r-t+1, 1), l-1);
}
//left
k1 = max(0, l-t-1);
for (int i = (r-l+2)>>1; i; i >>= 1) {
while (k1+i <= r-t &&
spt.query(k1+i, r-t) >= max(mamid, spt.query(max(l, k1+i+1), k1+i+t)))
k1 += i;
}
int leftbound = l-t-1;
//find furthest points -> <-
if (k1 > max(0, leftbound)) {
int pos = max(0, l-t-1), ma =
spt.query(pos+1, r-t);
for (int i = (r-l+2)>>1; i; i >>= 1) {
while (pos+i < k1 &&
spt.query(pos+i, r-t) < ma) pos += i;
}
++pos;
if (pos < k1) ans += ps1[k1]-ps1[pos];
ans += (ll)a[pos]*(min(pos, k1)-leftbound);
leftbound = k1;
// cout << pos << ' ' << k1 << ' ' << ans << "\n";
}
if (k1 > max(0, l-t-1)) k2 = k1;
else k2 = l-t-1;
for (int i = (r-l+2)>>1; i; i >>= 1) {
while (k2+i <= r-t &&
mamid >= spt.query(l, k2+i+t))
k2 += i;
}
ans += (ll)mamid*(k2-leftbound);
leftbound = k2;
// cout << k2 << ' ' << ans << "\n";
if (k2 < r-t) {
int pos = r-t+1, ma = spt.query(max(l, r-t), r);
for (int i = (r-l+2)>>1; i; i>>=1) {
while (pos-i > l-t &&
spt.query(pos-i+t, r) < ma) pos -= i;
}
--pos;
k2 += t;
pos += t;
if (pos > k2) ans += ps2[k2+1]-ps2[pos];
ans += (ll)a[pos]*(r-max(k2, pos-1));
// cout << pos << "\n";
}
cout << ans;
}
void solve() {
//prep
spt.init(n, a);
//prefix
vector<int> id;
a[0] = a[n+1] = INT_MAX;
id.pb(0);
ps1[0] = 0;
for (int i = 1; i <= n; i++) {
while (a[i] >= a[id.back()]) id.pop_back();
int las = id.back();
ps1[i] = (ll)a[i]*(i-las) + ps1[las];
id.pb(i);
}
id.clear();
id.pb(n+1);
ps2[n+1] = 0;
for (int i = n; i; i--) {
while (a[i] >= a[id.back()]) id.pop_back();
int las = id.back();
ps2[i] = (ll)a[i]*(las-i) + ps2[las];
id.pb(i);
}
// for (int i = 1; i <= n; i++) {
// cout << ps1[i] << ' ';
// }
// cout << "\n";
// for (int i = 1; i <= n; i++) {
// cout << ps2[i] << ' ';
// }
// cout << "\n";
//solve query
while (q--) {
int l, r, t;
cin >> t >> l >> r;
solvequery(t, l, r);
cout << "\n";
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// #define name "task"
// if (fopen(name".inp", "r")) {
// freopen(name".inp", "r", stdin);
// freopen(name".out", "w", stdout);
// }
cin >> n >> q;
for (int i = 1; i <= n ;i++) {
cin >> a[i];
}
//stress
if (sub1::check()) return sub1::solve(), 0;
return sub5::solve(), 0;
}
/*
5 1
9 3 2 6 5
3 2 5
5 5
9 3 2 6 5
1 1 3
2 1 5
3 2 5
4 3 3
5 3 5
*/
