#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for (int i = (r); i >= (l); --i)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cerr << '\n'; FOR(_, l, r) DB1(A, _); cerr << '\n';}
#define sz(x) ((int) (x).size())
#define pb push_back
#define eb emplace_back
#define pf push_front
#define F first
#define S second
#define next ___next
#define prev ___prev
#define y1 ___y1
#define left ___left
#define right ___right
#define y0 ___y0
#define div ___div
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
typedef pair<ll, int> ii;
typedef array<int, 3> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vl;
template<typename T>
struct FT {
vector<T> fenw;
FT() {}
FT(int N) : fenw(N + 1, 0) {}
void upd(int x, T v) {
// case x < 1?
assert(x > 0);
for (; x < sz(fenw); x += x & -x) {
fenw[x] += v;
}
}
T query(int x) {
// case x >= sz(fenw)?
assert(x < sz(fenw));
T ans = 0;
for (; x > 0; x -= x & -x) ans += fenw[x];
return ans;
}
T query(int l, int r) {
return query(r) - query(l - 1);
}
};
const int N = 2e5 + 2;
int n, q, ans[N], s[N];
viii qu[N];
vii upd_list[N][6]; // {v, pos}
FT<ll> fw[6];
// fw[0] ~ sum of v of open segments (to do: cur_time*sum_v - (0 - 1)*v) ~ all segments start at time 0
// fw[1] ~ sum of (left-1)*v of open segments (to do: pos*sum_v -(left - 1)*v)
// fw[2] ~ sum of (left-1)*v of closed segments
// fw[3] ~ sum of v of left closed segments
// fw[4] ~ sum of right*v of closed segments
// fw[5] ~ sum of v of right closed segments
void push_upd_events(int l, int r, int v)
{
if (l > r) return;
assert(l >= 1 && r <= 2 * n);
upd_list[0][0].pb({v, l});
upd_list[0][1].pb({(l - 1) * 1LL * v, l});
int end_time = r - l + 1;
upd_list[end_time][0].pb({-v, l});
upd_list[end_time][1].pb({-(l - 1) * 1LL * v, l});
upd_list[end_time][2].pb({(l - 1) * 1LL * v, l});
upd_list[end_time][3].pb({v, l});
upd_list[end_time][4].pb({r * 1LL * v, r});
upd_list[end_time][5].pb({v, r});
}
void push_raw_upd_events(int l, int r, int t, int v)
{
l += n, r += n;
int L = l - t;
push_upd_events(L, l - 1, -v);
push_upd_events(L, r, v);
}
int D[N], top, right[N];
void build_upd_list()
{
FOR(i, 0, 5) fw[i] = FT<ll> (2 * n);
D[0] = n + 1;
FORD(i, n, 1)
{
while (top && s[D[top]] < s[i])
{
push_raw_upd_events(D[top], right[D[top]], D[top] - i, -s[D[top]]);
top--;
}
right[i] = D[top] - 1;
push_raw_upd_events(i, right[i], 0, s[i]);
D[++top] = i;
}
}
ll cal(int pos, int cur_time)
{
if (pos == 0) return 0;
pos += n;
ll res = 0;
// open segments
ll sum_v = fw[0].query(pos - cur_time);
res += sum_v * (cur_time + 1);
ll sum_left = fw[1].query(pos - cur_time + 1, pos);
sum_v = fw[0].query(pos - cur_time + 1, pos);
res += pos * sum_v - sum_left;
// close segments
sum_v = fw[3].query(pos);
sum_left = fw[2].query(pos);
res += pos * sum_v - sum_left;
sum_v = fw[5].query(pos);
ll sum_right = fw[4].query(pos);
res += sum_right - pos * sum_v;
return res;
}
int main()
{
#ifdef HynDuf
freopen("inp.txt", "r", stdin);
#else
ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif
cin >> n >> q;
FOR(i, 1, n) cin >> s[i];
FOR(i, 1, q)
{
int l, r, t;
cin >> t >> l >> r;
qu[t].pb({l, r, i});
}
build_upd_list();
FOR(cur_time, 0, n)
{
FOR(i, 0, 5) for (ii &v : upd_list[cur_time][i]) fw[i].upd(v.S, v.F);
for (auto &Q : qu[cur_time]) ans[Q[2]] = cal(Q[1], cur_time) - cal(Q[0] - 1, cur_time);
}
FOR(i, 1, q) cout << ans[i] << '\n';
return 0;
}
