#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <random>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
const int INF = 1e9;
const int N = 400010;
struct Fenwick {
int n;
vector<ll> f;
void upd(int ind, int d) {
for (int i = ind + 1; i <= n; i += i & -i) {
f[i] += d;
}
}
ll get(int r) {
ll sum = 0;
for (int i = r; i > 0; i -= i & -i) {
sum += f[i];
}
return sum;
}
ll get(int l, int r) {
if (l >= r) {
return 0;
}
return get(r) - get(l);
}
Fenwick(int n_ = 0) : n(n_) {
f.assign(n + 1, 0ll);
}
};
int n, q;
int s[N];
int t[N], L[N], R[N];
vector<int> by_t[N];
ll ans[N];
pair<int, int> mx[2 * N];
vector<pair<int, int>> updl[N], updr[N];
Fenwick fl, fr;
void add(int l, int r, int ind, int d, int type) {
if (type == 0) {
updl[l].push_back({ind, d});
updl[r + 1].push_back({ind, -d});
} else {
updr[l].push_back({ind, d});
updr[r + 1].push_back({ind, -d});
}
}
pair<int, int> get_max(int l, int r) {
l += n, r += n;
pair<int, int> res = {-INF, -INF};
while (l < r) {
if (l & 1) {
res = max(res, mx[l]);
++l;
}
if (r & 1) {
--r;
res = max(res, mx[r]);
}
l >>= 1, r >>= 1;
}
return res;
}
void rec(int l, int r) {
if (l > r) {
return;
}
int m = get_max(l, r + 1).second;
rec(l, m - 1);
rec(m + 1, r);
if (m - l < r - m) {
for (int i = l; i <= m; ++i) {
add(m - i + 1, r - i + 1, i, s[m], 0);
}
} else {
for (int i = m; i <= r; ++i) {
add(i - m + 1, i - l + 1, i, s[m], 1);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
for (int i = 0; i < n; ++i) {
s[i + n] = s[i];
s[i] = -INF;
}
for (int i = 0; i < q; ++i) {
cin >> t[i] >> L[i] >> R[i];
--L[i];
++t[i];
L[i] += n, R[i] += n;
by_t[t[i]].push_back(i);
}
n *= 2;
for (int i = 0; i < n; ++i) {
mx[i + n] = {s[i], i};
}
for (int i = n - 1; i > 0; --i) {
mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
}
rec(0, n - 1);
fl = fr = Fenwick(n);
for (int t = 1; t <= n; ++t) {
for (auto [ind, d] : updl[t]) {
fl.upd(ind, d);
}
for (auto [ind, d] : updr[t]) {
fr.upd(ind, d);
}
for (int i : by_t[t]) {
ans[i] += fr.get(L[i], R[i]);
ans[i] += fl.get(L[i] - t + 1, R[i] - t + 1);
}
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << "\n";
}
return 0;
}
