#include <sys/time.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 200000;
const int Q = 200000;
const int N_ = 2000000;
unsigned int RNG = 1;
void srand() {
struct timeval tv;
gettimeofday(&tv, NULL);
RNG = tv.tv_sec ^ tv.tv_usec;
}
int rand() {
return (RNG *= 3) >> 1;
}
int aa[N], qul[N], qur[N], tt[Q], ll_[Q], rr_[Q], hh[Q];
int zz[N_], ll[N_], rr[N_], sz[N_], bb[N_], n_, u_, l_, r_;
long long ss[N_], ans[Q];
int node(int a) {
n_++;
zz[n_] = rand();
sz[n_] = 1;
bb[n_] = ss[n_] = a;
return n_;
}
void pul(int u) {
int l = ll[u], r = rr[u];
sz[u] = sz[l] + 1 + sz[r];
ss[u] = ss[l] + bb[u] + ss[r];
}
void split(int u, int i) {
if (!u) {
u_ = l_ = r_ = 0;
return;
}
if (i == sz[ll[u]]) {
u_ = u, l_ = ll[u], r_ = rr[u];
ll[u] = rr[u] = 0;
} else if (i < sz[ll[u]]) {
split(ll[u], i);
ll[u] = r_, r_ = u;
} else {
split(rr[u], i - sz[ll[u]] - 1);
rr[u] = l_, l_ = u;
}
pul(u);
}
int merge(int u, int v) {
if (!u)
return v;
if (!v)
return u;
if (zz[u] > zz[v]) {
rr[u] = merge(rr[u], v);
pul(u);
return u;
} else {
ll[v] = merge(u, ll[v]);
pul(v);
return v;
}
}
int query_a(int u, int i) {
while (i != sz[ll[u]])
if (i < sz[ll[u]])
u = ll[u];
else {
i -= sz[ll[u]] + 1;
u = rr[u];
}
return bb[u];
}
long long query_s(int u, int i) {
long long s = 0;
while (u && i >= 0)
if (i < sz[ll[u]])
u = ll[u];
else {
s += ss[ll[u]] + bb[u];
i -= sz[ll[u]] + 1;
u = rr[u];
}
return s;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
srand();
int n, q; cin >> n >> q;
for (int i = 0; i < n; i++)
cin >> aa[i];
for (int h = 0; h < q; h++)
cin >> tt[h] >> ll_[h] >> rr_[h], ll_[h]--, rr_[h]--, hh[h] = h;
sort(hh, hh + q, [] (int h0, int h1) { return tt[h0] < tt[h1]; });
int cnt = 0;
for (int l = 0, r; l + 1 < n; l = r + 1) {
for (r = l; r + 1 < n && aa[r] > aa[r + 1]; r++)
;
if (l < r)
qul[cnt] = l, qur[cnt] = r, cnt++;
}
for (int i = 0; i < n; i++)
u_ = merge(u_, node(aa[i]));
for (int g = 0, t = 1; t <= n; t++) {
int cnt_ = 0;
for (int z = 0; z < cnt; z++) {
int l = qul[z], r = qur[z];
split(u_, l);
int a = bb[u_], u = merge(l_, u_);
split(r_, r - sz[u]);
int v = merge(l_, r_);
u_ = merge(merge(u, node(a)), v);
l++;
if (r + 1 < n && query_a(u_, r) > query_a(u_, r + 1))
r++;
if (l < r)
qul[cnt_] = l, qur[cnt_] = r, cnt_++;
}
cnt = cnt_;
for (int h; g < q && tt[h = hh[g]] == t; g++) {
int l = ll_[h], r = rr_[h];
long long s = query_s(u_, r);
if (l)
s -= query_s(u_, l - 1);
ans[h] = s;
}
}
for (int h = 0; h < q; h++)
cout << ans[h] << '\n';
return 0;
}
