#include <bits/stdc++.h>
using namespace std;
const int N = 11000000;
long long s1 [N];	//ai之和
int ls [N],rs [N];
int ll [N],rr [N];
int sz [N];
int rt [N];
int cnt = 0;
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void write(long long x){
	static char buf[15];
  static int len = -1;
  if (x >= 0) {
    do {
      buf[++len] = x % 10 + 48, x /= 10;
    } while (x);
  } else {
    putchar('-');
    do {
      buf[++len] = -(x % 10) + 48, x /= 10;
    } while (x);
  }
  while (len >= 0) {
    putchar(buf[len]), --len;
  }
}

inline int _read(){
    char ch=nc();int sum=0;
    while(!(ch>='0'&&ch<='9'))ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum;
}
#define R 1000005
inline void add (int &u,int pre,int l,int r,int x) {	//x为位置 
	u = ++ cnt;
	sz [u] = sz [pre] + 1;
	ll [u] = l;rr [u] = r;
	s1 [u] = s1 [pre] + x;
	if (l == r) return ;
	int mid = (l + r) >> 1;
	if (x <= mid) {
		rs [u] = rs [pre];
		add (ls [u],ls [pre],l,mid,x);
	} else {
		ls [u] = ls [pre];
		add (rs [u],rs [pre],mid + 1,r,x);
	}
}
long long query (int u,int pre,int k,int ak) {
	long long num = sz [u] - sz [pre];
	if (!num) return 0;	//没人弄个p
	//看看是往左走还是右走 
	long long v = s1 [u] - s1 [pre] - num * (k + ak) - num * (num - 1) / 2;
	if (ll [u] >= k + ak) {	//全部向左走 
		return v;
	}
	if (rr [u] <= k + ak + num - 1) {
		return - v;
	}
	return query (ls [u],ls [pre],k,ak) + query (rs [u],rs [pre],k,ak + sz [ls [u]] - sz [ls [pre]]);
}
signed main () {
#ifndef ONLINE_JUDGE
	freopen ("shit.txt","r",stdin);
#endif
	int n = _read (),m = _read ();
	for (int i = 1;i <= n;++ i) {
		int x = _read ();
		add (rt [i],rt [i - 1],1,R,x);
	}
	while (m --) {
		int l = _read (),r = _read (),k = _read ();
		//printf ("%lld\n",query (rt [r],rt [l - 1],k,0));
		write (query (rt [r],rt [l - 1],k,0));
		putchar ('\n');
	}
	return 0;
}

%%%求助%%%