#include <bits/stdc++.h>
#define int long long
using namespace std;
struct query {
int t, l, r, index;
long long ans;
};
struct update {
int i, j;
};
const int MAX_N = 2e5;
int a[MAX_N + 1];
struct DSU {
vector<int> parent;
void init( int n ) {
parent.resize( n );
for ( int v = 0; v < n; v++ )
parent[v] = v;
}
int findParent( int v ) {
if ( parent[v] == v )
return v;
parent[v] = findParent( parent[v] );
return parent[v];
}
int unionn( int u, int v ) {
u = findParent( u );
v = findParent( v );
parent[v] = u;
}
};
struct range {
int l, r, t;
bool active = true;
vector<int> pos;
long long getSumPref( int tq, int rq ) {
rq -= l - 1;
int rep = min( rq, tq + 1 );
long long sum = (long long)a[pos.back()] * rep;
rq -= rep;
for ( int i = pos.size() - 2; i >= 0; i-- ) {
rep = min( rq, pos[i] - pos[i + 1] );
//printf( "%d %d %d %d %d\n", tq, rq, pos[i], pos[i + 1], sum );
sum += (long long)a[pos[i]] * rep;
rq -= rep;
}
//printf( "%d\n", sum );
return sum;
}
long long getSumRange( int tq, int lq, int rq ) {
lq = max( l, lq );
rq = min( r, rq );
return getSumPref( tq, rq ) - getSumPref( tq, lq - 1 );
}
void adopt( int tu, range &x ) {
x.active = false;
r = x.r;
int p = pos.back();
pos.clear();
swap( x.pos, pos );
pos.push_back( p );
t = tu;
}
};
vector<int> queriesByTime[MAX_N + 1];
vector<update> updatesByTime[MAX_N + 1];
range rangess[MAX_N + 1];
query queries[MAX_N + 1];
DSU rngs;
signed main() {
int n, q;
cin >> n >> q;
for ( int i = 1; i <= n; i++ )
cin >> a[i];
for ( int i = 0; i < q; i++ ) {
cin >> queries[i].t >> queries[i].l >> queries[i].r;
queries[i].index = i;
queriesByTime[queries[i].t].push_back( i );
}
vector<int> stack;
for ( int i = 1; i <= n; i++ ) {
while ( !stack.empty() && a[i] >= a[stack.back()] )
stack.pop_back();
if ( !stack.empty())
updatesByTime[i - stack.back()].push_back( { stack.back(), i } );
stack.push_back( i );
rangess[i] = { i, i, 1, true, { i + 1, i } };
}
rngs.init( n + 1 );
for ( int t = 1; t <= n; t++ ) {
reverse( updatesByTime[t].begin(), updatesByTime[t].end() );
for ( update u: updatesByTime[t] ) {
rangess[rngs.findParent( u.i )].adopt( t, rangess[rngs.findParent( u.j )] );
rngs.unionn( u.i, u.j );
}
/*for ( int i = 1; i <= n; i++ ) {
if ( rangess[i].active ) {
printf( "lrt %d %d %d\n", rangess[i].l, rangess[i].r, rangess[i].t );
for ( int j = rangess[i].pos.size() - 1; j >= 0; j-- )
printf( "%d ", rangess[i].pos[j] );
printf( "\n" );
}
}
printf( "\n" );*/
for ( int i: queriesByTime[t] ) {
int l = queries[i].l, r = queries[i].r;
//printf( "QUERY %d g %d %d\n", queries[i].index, l, r );
for ( int j = 1; j <= n; j++ ) {
if ( !rangess[j].active )
continue;
//printf( "kof %d %d\n", rangess[j].l, rangess[j].r );
if ( rangess[j].r < l || rangess[j].l > r )
continue;
long long sum = rangess[j].getSumRange( t, l, r );
//printf( "lrs %d %d %d\n", rangess[j].l, rangess[j].r, sum );
queries[i].ans += sum;
}
}
}
sort( queries, queries + q, []( query a, query b ) { return a.index < b.index; } );
for ( int i = 0; i < q; i++ )
cout << queries[i].ans << "\n";
return 0;
}
