#include <bits/stdc++.h>
#define int long long
using namespace std;
struct query {
int t, l, r;
long long ans;
};
const int MAX_N = 2e5;
const int MAX_Q = 2e5;
int n;
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];
set<int> increasingSegments, constantSegments;
void addIncreasingSegmentPerQuery( int i, int j, int t, long long sign ) {
queries[i].ans += sign * a[j] * max( 0LL, min( j + t - timeIncrease[j], queries[i].r ) - max( j, queries[i].l ) + 1 );//, printf( "increas %d %d\n", j, j + t - timeIncrease[j] );
}
void considerIncreasingSegmentsPerQuery( int i, int t, long long sign ) {
///if ( i != 0 )
// return;
int l = queries[i].l, r = queries[i].r;
int firstComplete = n + 1, lastComplete = 0;
auto p = increasingSegments.lower_bound( l );
if ( p != increasingSegments.end() )
firstComplete = *p;
if ( p != increasingSegments.begin() ) {
p--;
//addIncreasingSegmentPerQuery( i, *p, t, sign );
};
auto q = increasingSegments.upper_bound( r );
if ( q != increasingSegments.begin() ) {
q--;
//if ( q != p || p == increasingSegments.lower_bound( l ) )
//addIncreasingSegmentPerQuery( i, *q, t, sign );
int cnt = 0;
while ( (q--) != increasingSegments.begin() && (*q) + t - timeIncrease[*q] > queries[i].r )
cnt += 2;
assert( cnt <= 4 );
if ( (*q) + t - timeIncrease[*q] <= queries[i].r )
lastComplete = *q;
}
for ( int j: increasingSegments ) {
//printf( "incrs %d %d\n", j, queries[i].ans );
if ( firstComplete <= j && j <= lastComplete ) {
if ( queries[i].r < j + t - timeIncrease[j] )
exit( 1 );
queries[i].ans += sign * a[j] * (t - timeIncrease[j] + 1);
} else
addIncreasingSegmentPerQuery( i, j, t, sign );
}
}
void computeSegmentEvents( long long sign ) {
increasingSegments.clear();
constantSegments.clear();
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 );
considerIncreasingSegmentsPerQuery( i, t, sign );
for ( int j: constantSegments )
queries[i].ans += sign * a[j] * max( 0LL, 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" );
}
}
}
signed main() {
int 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( 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( -1 );
for ( int i = 0; i < q; i++ )
cout << queries[i].ans << "\n";
return 0;
}
