#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
#define bitcount(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
#define V vector
void read(int &a){
char c = getchar_unlocked(); a = 0;
while(c<'0' || '9'<c) c = getchar_unlocked();
while('0'<=c&&c<='9') a = (a<<3)+(a<<1)+c-'0', c = getchar_unlocked();
}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif
int inf = 2e09; ll infll = 2e18; int mod = (1<<23)*119+1;
int base = 1;
struct seg{
struct Node{
ll a, b; int la, lb;
Node(): a(0), b(0), la(0), lb(0) {}
Node(ll aa, ll bb, int laa, int lbb) : a(aa), b(bb), la(laa), lb(lbb) {}
};
vector<Node> t;
vector<ll> tab;
void merge(int &i){
t[i].a = t[i<<1].a + t[i<<1|1].a, t[i].b = t[i<<1].b + t[i<<1|1].b;
t[i].la = t[i<<1].la + t[i<<1|1].la, t[i].lb = t[i<<1].lb + t[i<<1|1].lb;
}
void init(int n, vector<ll> &a){
while(base < n) base <<= 1;
t.resize(base<<1); tab = a;
for(int i = 1; i <= n; ++i) t[i+base-1] = Node(a[i], a[i], 1, 1);
for(int i = base-1; i; --i) merge(i);
}
void update_point(int i, ll a, ll b, int la, int lb){ for(i += base-1, t[i] = Node(a, b, la, lb), i >>= 1; i; i >>= 1) merge(i); }
ll first_k(int i, int s, int e, int &x, int &y, int &k, int &T){
if(!k) return 0;
int mid = (s+e)>>1;
if(x <= s && e <= y){
int sum = t[i].la*T + t[i].lb;
if(sum <= k){ k -= sum; return t[i].a*T + t[i].b; }
else{
if(s != e) return first_k(i<<1, s, mid, x, y, k, T) + first_k(i<<1|1, mid+1, e, x, y, k, T);
else{ ll ret = tab[s]*k; k = 0; return ret; }
}
} ll ret = 0;
if(x <= mid) ret += first_k(i<<1, s, mid, x, y, k, T);
if(mid < y) ret += first_k(i<<1|1, mid+1, e, x, y, k, T);
return ret;
}
ll query_interval(int i, int s, int e, int &x, int &y, int &T){
if(x <= s && e <= y) return t[i].a*T + t[i].b;
int mid = (s+e)>>1; ll ret = 0;
if(x <= mid) ret += query_interval(i<<1, s, mid, x, y, T);
if(mid < y) ret += query_interval(i<<1|1, mid+1, e, x, y, T);
return ret;
}
ll query(int x, int y, int T){
if(x > y) return 0;
return query_interval(1, 1, base, x, y, T);
}
ll firstk(int x, int y, int k, int T){
if(x > y) return 0;
return first_k(1, 1, base, x, y, k, T);
}
};
struct ev{
int t, i;
ev(){}
ev(int tt, int ii) : t(tt), i(ii) {}
bool operator <(const ev &x) const{ return t < x.t; }
};
struct qr{
int a, b, i;
qr(){}
qr(int aa, int bb, int ii) : a(aa), b(bb), i(ii) {}
};
void answer(){
int n, q, tt; scanf("%d%d", &n, &q);
vector<ll> t(n+1);
vector<int> nxt(n+1), bef(n+1);
for(int i = 1; i <= n; ++i) read(tt), t[i] = tt;
seg seg; seg.init(n, t);
vector<int> st;
for(int i = 1; i <= n; ++i){
while(!st.empty() && t[st.back()] <= t[i]) st.pop_back();
if(st.empty()) bef[i] = n+1;
else bef[i] = i-st.back();
st.emplace_back(i);
} st = vector<int>();
for(int i = n; i; --i){
while(!st.empty() && t[st.back()] < t[i]) st.pop_back();
if(st.empty()) nxt[i] = n+1-i;
else nxt[i] = st.back()-i;
st.emplace_back(i);
} st = vector<int>();
vector<vector<ev>> event(n+2);
set<int> active;
for(int i = 1; i <= n; ++i) event[min(n+1, min(bef[i], nxt[i]))].emplace_back(0, i), event[min(n+1, max(bef[i], nxt[i]))].emplace_back(1, i),
event[min(n+1, min(bef[i], nxt[i])+max(bef[i], nxt[i]))].emplace_back(2, i), active.emplace(i);
vector<vector<qr>> queries(n+1);
for(int i = 1; i <= q; ++i){ int a, b, T; read(T), read(a), read(b), queries[T].emplace_back(a, b, i);}
vector<ll> result(q+1);
for(int T = 1; T <= n; ++T){
for(ev &u : event[T]){
if(!u.t){
if(u.i != 1) active.erase(u.i);
seg.update_point(u.i, 0, t[u.i]*T, 0, T);
} else if(u.t == 1) seg.update_point(u.i, -t[u.i], t[u.i]*(min(bef[u.i], nxt[u.i])+T-1), -1, min(bef[u.i], nxt[u.i])+T-1);
else seg.update_point(u.i, 0, 0, 0, 0);
}
for(qr &u : queries[T]){
auto it1 = active.upper_bound(u.a); it1 = prev(it1);
auto it2 = active.upper_bound(u.b); it2 = prev(it2);
result[u.i] = seg.query(*it1, (*it2)-1, T)-seg.firstk(*it1, u.a-1, u.a-(*it1), T)+seg.firstk(*it2, u.b, u.b-(*it2)+1, T);
}
}
for(int i = 1; i <= q; ++i) printf("%lld\n", result[i]);
}
int main(){
int T = 1; //scanf("%d", &T);
//ios_base::sync_with_stdio(0); cin.tie(0); cin >> T;
for(++T; --T; ) answer();
return 0;
}
