#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i, a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 6e5 + 10 , sq = 550, inf = 1e18+10 , mod = 10007 , lg = 20 ;
int a[maxn] , n , q ;
struct fen{
int f1[maxn] , f2[maxn] ;
void upd(int id ,int x ,int y ){
id += n+1 ;
while(id <= 2*n+q+1){
f1[id] += x*y ;
f2[id] += y ;
id += id&-id;
}
}
int que(int x ,int w){
int s1 =0 , s2 =0 ;
x += n+1 ;
while(x){
s1 += f1[x] ;
s2 += f2[x] ;
x -= x&-x ;
}
return s2*w - s1 ;
}
int bz(int l , int r , int x){
return (que(r, x) - que(l-1 , x)) ;
}
};
fen f1 , f2 , f3 ;
int d1[maxn] , d2[maxn] , ans[maxn] ;
vector <int> u1[maxn];
vector <pii> up[maxn] ;
vector <pair<pii,int> > q1[maxn] ;
void add(int x , int w ,int t){
up[t].pb({x,w}) ;
}
void c1(){
vector <int> vec ;
rep(i ,1 ,n){
while(sz(vec) && a[vec.back()] <= a[i])vec.pop_back() ;
if(sz(vec) == 0)d1[i] = 0 ;
else d1[i] = vec.back() ;
vec.pb(i) ;
}
vec.clear() ;
per(i , n , 1){
while(sz(vec) && a[vec.back()] < a[i])vec.pop_back() ;
if(sz(vec) == 0)d2[i] = n+1 ;
else d2[i] = vec.back() ;
vec.pb(i) ;
}
rep(i ,1 ,n)u1[d1[i]].pb(i) ;
rep(i ,1 ,n){
vector <pii> f;
f.pb({i,a[i]}) ;
for(int x : u1[i]){
f.pb({x , a[i]-a[x]}) ;
}
f.pb({d2[i] , 0}) ;
rep(j , 0, sz(f)-2){
int ti = f[j].F - i ;
add(f[j].F, f[j].S , ti);
add(f[j+1].F , -f[j].S , ti+f[j+1].F-f[j].F) ;
}
}
}
void upd(int x ,int w , int ti){
if(x==n+1)return ;
f1.upd(x , ti , w) ;
f2.upd(ti-x+1 , ti-x+1 ,w) ;
f3.upd(x , ti-x+1 , w) ;
}
int sl(int x , int ti){
int ans = 0 ;
ans += f1.bz(1 , x , ti);
ans -= f2.bz(-n , ti-x , ti-x) ;
ans += f3.bz(x+1 , n , ti-x) ;
return ans ;
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q;
rep(i , 1, n){
cin >> a[i] ;
}
c1() ;
rep(i ,1 ,q){
int l, r , ti ;
cin >> ti >> l >> r ;
q1[ti].pb({{l,r} , i}) ;
}
rep(i , 0, n){
for(auto [x,w] : up[i]){
upd(x , w , i-1) ;
}
for(auto [b,j] : q1[i]){
ans[j] += sl(b.S,i) ;
ans[j] -= sl(b.F-1 ,i) ;
}
}
rep(i ,1 , q){
cout << ans[i] << "\n" ;
}
}
/*
*/
