#include <bits/stdc++.h>
#define int long long
using namespace std;
struct query {
int t, l, r, index, ans;
};
struct update {
int i, j;
};
const int MAX_N = 2e5;
int a[MAX_N + 1];
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 - t + 1 );
long long sum = a[pos.back()] * rep;
rq -= rep;
for ( int i = pos.size() - 1; i >= 1; i-- ) {
rep = min( rq, pos[i - 1] - pos[i] );
//printf( "%d %d %d %d\n", tq, rq, pos[i], pos[i - 1] );
sum += (long long)a[pos[i]] * rep;
rq -= rep;
}
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];
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 } };
}
for ( int t = 1; t <= n; t++ ) {
reverse( updatesByTime[t].begin(), updatesByTime[t].end() );
for ( update u: updatesByTime[t] )
rangess[u.i].adopt( t, rangess[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\n", queries[i].index );
for ( int j = 1; j <= n; j++ ) {
if ( !rangess[j].active )
continue;
if ( rangess[j].r < l || rangess[j].l > r )
continue;
long long sum = rangess[j].getSumRange( t, l, r );;
queries[i].ans += sum;
//printf( "lrs %d %d %d\n", rangess[j].l, rangess[j].r, 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;
}
