/** - dwuy -
／＞ フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long
using namespace std;
typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;
const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 200005;
struct Node{
int cnts, cntt, sums, sumt, lazy;
Node() : cnts(0), cntt(0), sums(0), sumt(0), lazy(0) {}
};
struct SMT{
int n;
vector<Node> tree;
SMT(int n = 0){
this->n = n;
this->tree.assign(n<<2|3, Node());
}
void down(int id){
if(tree[id].lazy == 0) return;
int val = tree[id].lazy;
int ID = id<<1;
tree[ID].lazy += val;
tree[ID].cnts += val*tree[ID].cntt;
tree[ID].sums += val*tree[ID].sumt;
tree[ID|1].lazy += val;
tree[ID|1].cnts += val*tree[ID|1].cntt;
tree[ID|1].sums += val*tree[ID|1].sumt;
tree[id].lazy = 0;
}
Node combine(Node a, Node b){
Node res;
res.cntt = a.cntt + b.cntt;
res.cnts = a.cnts + b.cnts;
res.sumt = a.sumt + b.sumt;
res.sums = a.sums + b.sums;
return res;
}
void byebye(int pos){
int id = 1;
for(int lo=1, hi=n; lo<hi;){
int mid = (lo + hi)>>1;
down(id);
if(pos <= mid) hi = mid, id = id<<1;
else lo = mid + 1, id = id<<1|1;
}
tree[id] = Node();
for(id>>=1; id; id>>=1) tree[id] = combine(tree[id<<1], tree[id<<1|1]);
}
void update(int pos, int val, int cnt){
int id = 1;
for(int lo=1, hi=n; lo<hi;){
int mid = (lo + hi)>>1;
down(id);
if(pos <= mid) hi = mid, id = id<<1;
else lo = mid + 1, id = id<<1|1;
}
tree[id].cntt = 1;
tree[id].cnts = cnt;
tree[id].sumt = val;
tree[id].sums = val*cnt;
for(id>>=1; id; id>>=1) tree[id] = combine(tree[id<<1], tree[id<<1|1]);
}
void query(int f){
tree[1].lazy += f;
tree[1].cnts += tree[1].cntt * f;
tree[1].sums += tree[1].sumt * f;
}
};
int n, q;
int a[MX];
int pl[MX];
int pr[MX];
int ans[MX];
int T[MX], L[MX], R[MX];
vector<int> G[MX];
vector<int> P0[MX];
vector<int> P1[MX];
vector<int> P2[MX];
void nhap(){
cin >> n >> q;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=q; i++){
cin >> T[i] >> L[i] >> R[i];
G[T[i]].push_back(i);
}
}
void calcPL(){
stack<int> st;
for(int i=1; i<=n; i++){
while(st.size() && a[st.top()] < a[i]) st.pop();
pl[i] = st.size()? st.top() : -1e9;
st.push(i);
}
}
void calcPR(){
stack<int> st;
for(int i=n; i>=1; i--){
while(st.size() && a[st.top()] <= a[i]) st.pop();
pr[i] = st.size()? st.top() : n + 1;
st.push(i);
}
}
void solve(){
calcPL();
calcPR();
for(int i=1; i<=n; i++){
P0[min(pr[i] - i, i - pl[i])].push_back(i);
if(pl[i] > 0){
P1[max(pr[i] - i, i - pl[i])].push_back(i);
P2[pr[i] - pl[i]].push_back(i);
}
}
SMT Add(n);
SMT Keep(n);
SMT Die(n);
for(int i=1; i<=n; i++) Add.update(i, a[i], 1);
for(int t=1; t<=n; t++){
for(int u: P0[t]){
Add.byebye(u);
Keep.update(u, a[u], min(pr[u] - u, u - pl[u]));
}
for(int u: P1[t]){
Keep.byebye(u);
Die.update(u, a[u], min(pr[u] - u, u - pl[u]));
}
for(int u: P2[t]){
Die.byebye(u);
}
Add.query(1);
Die.query(-1);
for(int i: G[t]){
int l = L[i];
int r = R[i];
function<int(int)> dwuy = [&](int k) -> int {
int res = 0;
int id, lo, hi;
for(id=1, lo=1, hi=n; lo<hi;){
int mid = (lo + hi)>>1;
Add.down(id);
Die.down(id);
int cnt = Add.tree[id<<1].cnts + Die.tree[id<<1].cnts + Keep.tree[id<<1].cnts;
if(cnt < k){
k -= cnt;
res += Add.tree[id<<1].sums + Keep.tree[id<<1].sums + Die.tree[id<<1].sums;
id = id<<1|1;
lo = mid + 1;
}
else hi = mid, id = id<<1;
}
int cnt = Add.tree[id].cnts + Die.tree[id].cnts + Keep.tree[id].cnts;
if(cnt < k){
k -= cnt;
res += Add.tree[id].sums + Keep.tree[id].sums + Die.tree[id].sums;
lo++;
}
return res + a[lo] * k;
};
ans[i] = dwuy(r) - dwuy(l - 1);
}
}
for(int i=1; i<=q; i++) cout << ans[i] << '\n';
}
int32_t main(){
fastIO;
//file(TASK);
nhap();
solve();
return 0;
}
/*
20 20
2 1 2 2 1 1 1 1 2 2 2 1 2 1 1 2 1 2 1 1
1 1 14
2 3 18
4 10 15
8 2 17
9 20 20
4 8 19
7 2 20
11 1 5
13 2 8
20 1 20
2 12 15
7 1 14
12 7 18
14 2 17
9 19 20
12 12 12
6 2 15
11 2 15
19 12 17
4 1 20
*/
