#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}

#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
  return x*w;
}

const int N=4e5+5,inf=0x3f3f3f3f;
int n,Q,B,s[N],l[N],r[N],t[N],d[N],a[N],b[N],f[20][N],ans[N];

int qry(int r,int k) {
  ++k; k=min(k,r); int h=__lg(k);
  return max(f[h][r-k+1],f[h][r-(1<<h)+1]);
}
void work(int L,int R) {
  rep(i,0,n+1) d[i]=0;
  rep(i,1,R) {
    if(i+b[i]<L) continue;
    else if(i<L) {
      d[L-i]+=s[i];
      d[L-i+a[i]+1]-=s[i];
    } else {
      d[0]+=s[i];
      d[a[i]+1]-=s[i];
    }
    d[min(R-i,b[i])+1]-=s[i];
    d[min(R-i,b[i])+a[i]+2]+=s[i];
  }
  rep(i,1,n) d[i]+=d[i-1];
  rep(i,1,n) d[i]+=d[i-1];
  rep(i,1,Q) {
    int x=max(L,l[i]), y=min(R,r[i]);
    if(x>y) continue;
    else if(x==L&&y==R) ans[i]+=d[t[i]];
    else {rep(j,x,y) ans[i]+=qry(j,t[i]);}
  }
}

signed main() {
  n=read(), Q=read(), B=sqrt(n);
  rep(i,1,n) s[i]=read(), f[0][i]=s[i];
  s[n+1]=inf; f[0][n+1]=inf;
  rep(h,1,18) rep(i,1,n) if(i+(1<<h)-1<=n+1)
    f[h][i]=max(f[h-1][i],f[h-1][i+(1<<h-1)]);
  rep(i,1,n) {
    int l=1, r=i; a[i]=n+1;
    while(l<=r) {
      int mid=l+r>>1;
      if(qry(i,mid)<=s[i]) l=mid+1;
      else r=mid-1, a[i]=mid-1;
    }
    l=1, r=n-i+1; b[i]=n+1;
    while(l<=r) {
      int mid=l+r>>1;
      if(qry(i+mid,mid-1)<s[i]) l=mid+1;
      else r=mid-1, b[i]=mid-1;
    }
  }
  rep(i,1,Q) t[i]=read(), l[i]=read(), r[i]=read();
  for(int pos=1;pos<=n;pos+=B) work(pos,min(n,pos+B-1));
  rep(i,1,Q) printf("%lld\n",ans[i]);
  return 0;
}