#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
const int N = 200011;
struct Fenwick
{
vector<ll> t;
Fenwick(int n)
{
t.assign(n+1,0);
}
void reset(int n)
{
t.assign(n+1, 0);
}
void update(int p, ll v)
{
for (; p < (int)t.size(); p += (p&(-p))) t[p] += v;
}
ll query(int r) //finds [1, r] sum
{
ll sum = 0;
for (; r; r -= (r&(-r))) sum += t[r];
return sum;
}
ll query(int l, int r) //finds [l, r] sum
{
if(l == 0) return query(r);
return query(r) - query(l-1);
}
};
vector<ii> queries[N+11];
ll ans[N+11];
ll a[N+11];
int par[N+11];
const int C = N+4;
Fenwick F(2*N+11),F2(2*N+11),Fsum(2*N+11),F2sum(2*N+11);
Fenwick F3(2*N+11),F3sum(2*N+11);
ll shift=-C;
int subsiz[N+11];
vi adj[N+11];
ll summax;
void addval(int x, ll val)
{
F2.update(x-shift,val);
F2sum.update(x-shift,val*(x-shift));
}
int calcsiz(int u)
{
subsiz[u]=1;
for(int v:adj[u])
{
subsiz[u]+=subsiz[v];
}
return subsiz[u];
}
void quit(int id)
{
ll subsz = calcsiz(id);
if(par[id]!=-1)
{
subsz+=(id-par[id]-1);
ll val = a[par[id]]-a[id];
F2.update(subsz-shift,-val);
F2sum.update(subsz-shift,-val*1LL*(subsz-shift));
F.update(subsz+C,val);
Fsum.update(subsz+C,val*subsz);
}
//if(par[id]!=-1) subsz--;
}
ll query(int t)
{
ll sum1 = Fsum.query(1,t+C)+ll(t)*F.query(t+C+1,2*N+10);
ll sum2 = F2sum.query(1,t-shift)+ll(shift)*F2.query(1,t-shift)+ll(t)*F2.query(t-shift+1,2*N+10);
sum2+=F3sum.query(t+1+C,2*N+10)-F3.query(t+1+C,2*N+10)*ll(t);
return sum1+sum2+summax;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n,q; cin>>n>>q;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<q;i++)
{
int t,l,r; cin>>t>>l>>r;
l--; r--;
queries[r].pb({i,t});
if(l>0) queries[l-1].pb({i,-t});
}
memset(par,-1,sizeof(par));
for(int i=0;i<n;i++)
{
//add the value
summax+=a[i];
if(i==0)
{
//addval(0,a[0]);
//summax+=a[0];
}
else
{
int cur=i-1;
while(cur>=0&&a[i]>=a[cur])
{
quit(cur);
cur=par[cur];
}
shift++;
par[i]=cur;
//int val = 0;
//if root then initial value = 1
if(par[i]!=-1)
{
summax-=(a[par[i]]-a[i])*1LL*(i-par[i]-1);
F3.update(i-par[i]-1+C,a[par[i]]-a[i]);
F3sum.update(i-par[i]-1+C,(i-par[i]-1)*1LL*(a[par[i]]-a[i]));
//cerr<<"ADD VAL (NODE = "<<i<<") : "<<1+i-par[i]-1<<'\n';
addval(1+i-par[i]-1,a[par[i]]-a[i]);
adj[par[i]].pb(i);
}
//else summax+=a[i];
}
//solve the queries
for(ii x:queries[i])
{
ll tmp = query(abs(x.se));
ll sum=0;
for(int j=0;j<=i;j++)
{
ll mx=0;
for(int k=j;k>=max(0,j-(abs(x.se)));k--)
{
mx=max(mx,a[k]);
}
sum+=mx;
}
//cerr<<"QUERY TILL "<<i<<" WITH T = "<<abs(x.se)<<": "<<tmp<<' '<<sum<<'\n';
if(x.se<0)
{
ans[x.fi]-=tmp;
}
else
{
ans[x.fi]+=tmp;
}
}
}
for(int i=0;i<q;i++)
{
cout<<ans[i]<<'\n';
}
}
