#include <bits/stdc++.h>
using namespace std;
struct query {
int t, l, r;
long long ans;
};
struct AIB {
int n;
vector<long long> aib;
void init( int _n ) {
n = _n;
aib.resize( n + 1 );
}
void update( int i, long long x ) {
while ( i <= n ) {
aib[i] += x;
i += (i & -i);
}
}
long long query( int i ) {
long long sum = 0;
while ( i > 0 ) {
sum += aib[i];
i -= (i & -i);
}
return sum;
}
};
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];
vector<int> queriesByTime[MAX_N + 1];
vector<int> stopIncreasingR[MAX_N + 1], startDecreasingL[MAX_N + 1], stopAll[MAX_N + 1];
query queries[MAX_Q];
set<int> increasingR, constantR, constantL, decreasingL;
AIB sumIncreasingR, sumIncreasingRI;
AIB sumConstantR, sumConstantRI;
AIB sumConstantL, sumConstantLI;
AIB sumDecreasingL, sumDecreasingLI;
void toggleIncreasingR( int i ) {
if ( increasingR.find( i ) == increasingR.end() ) {
increasingR.insert( i );
sumIncreasingR.update( i, a[i] );
sumIncreasingRI.update( i, (long long)a[i] * i );
} else {
increasingR.erase( i );
sumIncreasingR.update( i, -a[i] );
sumIncreasingRI.update( i, -(long long)a[i] * i );
}
}
void toggleConstantR( int i ) {
if ( constantR.find( i ) == constantR.end() ) {
constantR.insert( i );
sumConstantR.update( i, a[i] );
sumConstantRI.update( i, (long long)a[i] * i );
} else {
constantR.erase( i );
sumConstantR.update( i, -a[i] );
sumConstantRI.update( i, -(long long)a[i] * i );
}
}
void toggleConstantL( int i ) {
if ( constantL.find( i ) == constantL.end() ) {
constantL.insert( i );
sumConstantL.update( i, a[i] );
sumConstantLI.update( i, (long long)a[i] * i );
} else {
constantL.erase( i );
sumConstantL.update( i, -a[i] );
sumConstantLI.update( i, -(long long)a[i] * i );
}
}
void toggleDecreasingL( int i ) {
if ( decreasingL.find( i ) == decreasingL.end() ) {
decreasingL.insert( i );
sumDecreasingL.update( i, a[i] );
sumDecreasingLI.update( i, (long long)a[i] * i );
} else {
decreasingL.erase( i );
sumDecreasingL.update( i, -a[i] );
sumDecreasingLI.update( i, -(long long)a[i] * i );
}
}
long long handleIncreasingR( int t, int p ) {
auto ptr = increasingR.upper_bound( p - t );
int pos = (ptr == increasingR.end() ? n + 1 : *ptr);
long long sum = sumIncreasingRI.query( pos - 1 ) + sumIncreasingR.query( pos - 1 ) * t + (sumIncreasingR.query( n ) - sumIncreasingR.query( pos - 1 )) * p;
return sum;
}
long long handleConstantR( int t, int p ) {
long long sum = 0;
for ( int i: constantR )
sum += (long long)min( rightt[i] - 1, p ) * a[i];
return sum;
}
long long handleConstantL( int t, int p ) {
long long sum = 0;
for ( int i: constantL )
sum -= (long long)min( i - 1, p ) * a[i];
return sum;
}
long long handleDecreasingL( int t, int p ) {
long long sum = 0;
for ( int i: decreasingL )
sum -= (long long)min( t + leftt[i], p ) * a[i];
return sum;
}
long long getSumPrefix( int t, int p ) {
//printf( "%d %d\n", t, p );
long long sum = 0;
sum += handleIncreasingR( t, p );
sum += handleConstantR( t, p );
sum += handleConstantL( t, p );
sum += handleDecreasingL( t, p );
return sum;
}
int 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 );
}
sumIncreasingR.init( n );
sumIncreasingRI.init( n );
for ( int i = 1; i <= n; i++ ) {
int goDown = i - leftt[i], goIncreasing = rightt[i] - i;
toggleIncreasingR( i );
toggleConstantL( i );
stopIncreasingR[goIncreasing].push_back( i );
startDecreasingL[goDown].push_back( i );
stopAll[goDown + goIncreasing - 1].push_back( i );
}
for ( int t = 1; t <= n; t++ ) {
for ( int i: stopIncreasingR[t] ) {
toggleIncreasingR( i );
toggleConstantR( i );
}
for ( int i: startDecreasingL[t] ) {
toggleConstantL( i );
toggleDecreasingL( i );
}
for ( int i: stopAll[t] ) {
toggleConstantR( i );
toggleDecreasingL( i );
}
/*printf( "timp\n" );
for ( int i: increasingR )
printf( "%d ", i );
printf( "\n" );
for ( int i: constantR )
printf( "%d ", i );
printf( "\n" );
for ( int i: constantL )
printf( "%d ", i );
printf( "\n" );
for ( int i: decreasingL )
printf( "%d ", i );
printf( "\n\n" );*/
for ( int i: queriesByTime[t] ) {
//printf( "query\n" );
queries[i].ans = getSumPrefix( t, queries[i].r ) - getSumPrefix( t, queries[i].l - 1 );
}
}
for ( int i = 0; i < q; i++ )
cout << queries[i].ans << "\n";
return 0;
}
