#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1<<19;
ll drz[2][2 * N], laz[2][2 * N];
vector<pair<pair<int, int>, int>> que[N];
vector<pair<pair<int, int>, int>> upd[2][N];
int tab[N], l[N], r[N];
ll answer[N];
void Push(int r, int v)
{
if(laz[r][v] == 0LL) return;
for(int s = v * 2; s <= v * 2 + 1; ++s)
{
drz[r][s] += laz[r][v] / 2LL;
laz[r][s] += laz[r][v] / 2LL;
}
laz[r][v] = 0LL;
}
void Add(int r, int v, int p, int k, int pz, int kz, ll x)
{
if(p > kz || k < pz) return;
if(p >= pz && k <= kz)
{
drz[r][v] += (ll)(k - p + 1) * x;
laz[r][v] += (ll)(k - p + 1) * x;
return;
}
Add(r, v * 2, p, (p + k) / 2, pz, kz, x);
Add(r, v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x);
drz[r][v] = drz[r][v * 2] + drz[r][v * 2 + 1] + laz[r][v];
}
inline void A(int r, int p, int k, int x)
{
Add(r, 1, 0, N - 1, p, k, x);
}
ll Query(int r, int v, int p, int k, int pz, int kz)
{
if(p > kz || k < pz) return 0LL;
if(p >= pz && k <= kz)
return drz[r][v];
Push(r, v);
ll a = Query(r, v * 2, p, (p + k) / 2, pz, kz);
a += Query(r, v * 2 + 1, (p + k) / 2 + 1, k, pz, kz);
return a;
}
inline ll Q(int r, int a, int b)
{
return Query(r, 1, 0, N - 1, a, b);
}
void DoT(int i, int j, int x)
{
//cout << "T: " << i << " " << j << " " << x << "\n";
upd[0][j].pb(make_pair(make_pair(i, N - 10), x));
upd[1][j].pb(make_pair(make_pair((i - j + 1) + (N / 2), N - 10), -x));
}
void Solve()
{
int n, q, a, b, c;
cin >> n >> q;
vector<int> cur = {0};
tab[0] = II;
for(int i = 1; i <= n; ++i)
{
cin >> tab[i];
while(tab[i] > tab[cur.back()]) cur.pop_back();
l[i] = cur.back();
cur.pb(i);
}
tab[n + 1] = II; cur = {n + 1};
for(int i = n; i >= 1; --i)
{
while(tab[i] >= tab[cur.back()]) cur.pop_back();
r[i] = cur.back();
cur.pb(i);
}
for(int i = 1; i <= q; ++i)
{
cin >> c >> a >> b;
++c; c = min(c, n);
que[c].pb(make_pair(make_pair(a, b), i));
}
for(int i = 1; i <= n; ++i)
{
int d = i - l[i], d2 = r[i] - i;
//cout << "\nD: " << i << " " << l[i] << " " << r[i] << "\n";
if(l[i] == 0) d = n;
DoT(i, 1, tab[i]);
DoT(i, d + 1, -tab[i]);
DoT(r[i], d2 + 1, -tab[i]);
DoT(r[i], d2 + d + 1, tab[i]);
}
for(int i = 1; i <= n; ++i)
{
for(int r = 0; r < 2; ++r)
for(int j = 0; j < (int)upd[r][i].size(); ++j)
A(r, upd[r][i][j].st.st, upd[r][i][j].st.nd, upd[r][i][j].nd);
for(int j = 0; j < (int)que[i].size(); ++j)
{
answer[que[i][j].nd] = Q(0, que[i][j].st.st, que[i][j].st.nd);
answer[que[i][j].nd] += Q(1, que[i][j].st.st - i + (N / 2), que[i][j].st.nd - i + (N / 2));
}
}
for(int i = 1; i <= q; ++i)
cout << answer[i] << "\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//int t; cin >> t;
//while(t--)
Solve();
return 0;
}
