#include <bits/stdc++.h>
using namespace std;
struct query {
int t, l, r;
long long ans;
};
const int MAX_N = 2e5;
const int MAX_Q = 2e5;
int a[MAX_N + 1], leftt[MAX_N + 1], rightt[MAX_N + 1], timeIncrease[MAX_N + 1];
vector<int> queriesByTime[MAX_N + 1];
vector<int> increasingSegmentsByTime[MAX_N + 1], constantSegmentsByTime[MAX_N + 1];
query queries[MAX_Q];
void computeSegmentEvents( int n, int sign ) {
set<int> increasingSegments, constantSegments;
for ( int t = 0; t <= n; t++ ) {
for ( int i: increasingSegmentsByTime[t] ) {
if ( increasingSegments.find( i ) == increasingSegments.end() )
increasingSegments.insert( i );
else
increasingSegments.erase( i );
}
for ( int i: constantSegmentsByTime[t] ) {
if ( constantSegments.find( i ) == constantSegments.end() )
constantSegments.insert( i );
else
constantSegments.erase( i );
}
for ( int i: queriesByTime[t] ) {
//printf( "QUERY %d\n", i );
for ( int j: increasingSegments )
queries[i].ans += sign * a[j] * max( 0, min( j + t - timeIncrease[j], queries[i].r ) - max( j, queries[i].l ) + 1 );//, printf( "increas %d %d\n", j, j + t - timeIncrease[j] );
for ( int j: constantSegments )
queries[i].ans += sign * a[j] * max( 0, min( rightt[j] - 1, queries[i].r ) - max( j, queries[i].l ) + 1 );//, printf( "cst %d %d\n", j, rightt[j - 1] - 1 );
//printf( "\n\n\n" );
}
}
}
int 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;
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() )
leftt[i] = stack.back();
else
leftt[i] = -(n + 1);
stack.push_back( i );
}
while ( !stack.empty() )
stack.pop_back();
for ( int i = n; i >= 1; i-- ) {
while ( !stack.empty() && a[i] > a[stack.back()] )
stack.pop_back();
if ( !stack.empty() )
rightt[i] = stack.back();
else
rightt[i] = (n + 1);
stack.push_back( i );
}
for ( int t = 0; t <= n; t++ ) {
increasingSegmentsByTime[t].clear();
constantSegmentsByTime[t].clear();
}
for ( int i = 1; i <= n; i++ ) { // update + on trapezoid
int goDown = i - leftt[i], goIncreasing = rightt[i] - i;
timeIncrease[i] = 0;
increasingSegmentsByTime[0].push_back( i );
increasingSegmentsByTime[goIncreasing].push_back( i );
constantSegmentsByTime[goIncreasing].push_back( i );
constantSegmentsByTime[goIncreasing + goDown - 1].push_back( i );
}
computeSegmentEvents( n, 1 );
for ( int t = 0; t <= n; t++ ) {
increasingSegmentsByTime[t].clear();
constantSegmentsByTime[t].clear();
}
for ( int i = 1; i <= n; i++ ) { // update - on triangle
int goDown = i - leftt[i], goIncreasing = rightt[i] - i;
timeIncrease[i] = goDown;
increasingSegmentsByTime[goDown].push_back( i );
increasingSegmentsByTime[goDown + goIncreasing - 1].push_back( i );
}
computeSegmentEvents( n, -1 );
for ( int i = 0; i < q; i++ )
cout << queries[i].ans << "\n";
return 0;
}
